手写哈希+只遍历r范围内的点
时间复杂度:$O((n+m)×4r²)$~$2×10^7$
//大佬思路:https://www.acwing.com/solution/content/111041/
import java.io.*;
import java.util.*;
public class Main{
static int N = 50010;
static PII[] bombs = new PII[N];
static int P = (int)1e9 + 1;
static int M = (int)1e6 + 3;
static long[] h = new long[M];///h[i]记录在哈希数组的i位置存的key, key = x * P + y
static int[] id = new int[M];//id[i]记录在哈希数组的i位置存的是哪个炸弹
static boolean[] st = new boolean[M];
//find(x,y)找到(x,y)在哈希数组存储位置的下标
static int find(int x, int y){
long key = x * P + y;
int t = (int)((key % M + M) % M);
while(h[t] != -1 && h[t] != key){
t ++;
if(t == M) t = 0;
}
return t;
}
static boolean check(int x1, int y1, int x2, int y2, int r){
if((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= r * r) return true;
else return false;
}
static void dfs(int x, int y, int r){
st[find(x, y)] = true;
for(int i = x - r; i <= x + r; i ++){
for(int j = y - r; j <= y + r; j ++){
int t = find(i, j);
if(id[t] != -1 && !st[t] && check(i, j, x, y, bombs[id[find(x, y)]].r)){
dfs(i, j, bombs[id[t]].r);
}
}
}
}
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int m = Integer.parseInt(s1[1]);
Arrays.fill(h, -1);
Arrays.fill(id, -1);
for(int i = 0; i < n; i ++){
String[] s2 = br.readLine().split(" ");
int x = Integer.parseInt(s2[0]);
int y = Integer.parseInt(s2[1]);
int r = Integer.parseInt(s2[2]);
bombs[i] = new PII(x, y, r);
int t = find(x, y);//找到该地雷的key在哈希数组中存储的下标
if(h[t] == -1) h[t] = x * P + y;//如果插入位置为空,则将key插入
if(id[t] == -1 || bombs[id[t]].r < r) id[t] = i;//id[i]=j表示第j个地雷的key记录在哈希数组下标为i的位置
}
for(int k = 0; k < m; k ++){
String[] s3 = br.readLine().split(" ");
int x = Integer.parseInt(s3[0]);
int y = Integer.parseInt(s3[1]);
int r = Integer.parseInt(s3[2]);
//只寻找圆心r范围内的点
for(int i = x - r; i <= x + r; i ++){
for(int j = y - r; j <= y + r; j ++){
int t = find(i, j);
if(id[t] != -1 && !st[t] && check(i, j, x, y, r)){
dfs(i, j, bombs[id[t]].r);
}
}
}
}
int res = 0;
for(int i = 0; i < n; i ++){
int x = bombs[i].x;
int y = bombs[i].y;
if(st[find(x, y)]) res ++;
}
System.out.println(res);
}
}
class PII{
int x;
int y;
int r;
public PII(int x, int y, int r){
this.x = x;
this.y = y;
this.r = r;
}
}
重写equals方法和hashCode方法
//通过了 4/11个数据
import java.io.*;
import java.util.*;
public class Main{
static int N = 50010;
static Map<PII,Integer> bombs = new HashMap<>();
static Map<PII,Integer> rocs = new HashMap<>();
static int n, m, cnt;
static void dfs(PII p, int num){
p.live = false;
cnt += num;
for(PII b: bombs.keySet()){
if((p.x - b.x) * (p.x - b.x) + (p.y - b.y) * (p.y - b.y) <= (p.r + b.r) * (p.r + b.r) && b.live){
dfs(b, bombs.get(b));
}
}
}
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
for(int i = 0; i < n; i ++){
String[] s2 = br.readLine().split(" ");
int x1 = Integer.parseInt(s2[0]);
int y1 = Integer.parseInt(s2[1]);
int r1 = Integer.parseInt(s2[2]);
PII pii1 = new PII(x1, y1, r1);
bombs.put(pii1, bombs.getOrDefault(pii1, 0) + 1);
}
for(int i = 0; i < m; i ++){
String[] s3 = br.readLine().split(" ");
int x2 = Integer.parseInt(s3[0]);
int y2 = Integer.parseInt(s3[1]);
int r2 = Integer.parseInt(s3[2]);
PII pii2 = new PII(x2, y2, r2);
rocs.put(pii2, rocs.getOrDefault(pii2, 0) + 1);
}
for(PII roc : rocs.keySet()){
dfs(roc, rocs.get(roc));
}
System.out.println(cnt - m);
}
}
class PII{
int x;
int y;
int r;
boolean live = true;
public PII(int x, int y, int r){
this.x = x;
this.y = y;
this.r = r;
}
@Override
public boolean equals(Object o){
if(this == o) return true;
if(!(o instanceof PII)) return false;
PII pii = (PII) o;
return this.x == pii.x && this.y == pii.y && this.r == pii.r;
}
@Override
public int hashCode(){
return Objects.hash(x, y, r);
}
}