题目描述

圆的爆炸范围 x^2 + y^2 <= r^2

样例

import java.util.*;

public class Main {

    //哈希表的大小最好是存的数据的两倍，n个9加上7或者是1后面n个0最后一位是3或7
    static final int N = 50010, M = 999997;

    static int n, m;
    //存放雷
    static Circle[] cir = new Circle[N];
    //哈希表(把坐标转化成整数)
    static long[] h = new long[M];
    //每一个点对应的雷的id是什么 如果多个雷都在同一个点，该点存放爆炸范围最大的雷
    static int[] id = new int[M];
    //表示该点是否被遍历过
    static boolean[] st = new boolean[M];

    static class Circle {
        int x, y, r;

        Circle(int x, int y, int r) {
            this.x = x;
            this.y = y;
            this.r = r;
        }
    }

    //x,y转化成long类型
    static long get_key(int x, int y) {
        return (long)x * 1000000001L + y;
    }

    //默写手写哈希表代码
    static int find(int x, int y) {
        long key = get_key(x, y);
        int t = (int) ((key % M + M) % M);

        while (h[t] != -1 && h[t] != key) {
            if (++t == M) {
                t = 0;
            }
        }
        return t;
    }

    static int sqr(int x) {
        return x * x;
    }

    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++) {
                //表示该点在爆炸范围内
                if (sqr(i - x) + sqr(j - y) <= sqr(r)) {
                    //求该点的哈希值
                    int t = find(i, j);
                    //如果这个点有雷，而且没有被搜过
                    if (id[t] != 0 && !st[t]) {
                        //我们就搜一下这个雷
                        dfs(i, j, cir[id[t]].r);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();

        //先把哈希表初始成为-1 表示这个坑没有被用过
        Arrays.fill(h, -1);

        for (int i = 1; i <= n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int r = scanner.nextInt();
            cir[i] = new Circle(x, y, r);

            int t = find(x, y);
            //如果哈希表这个坑位没有被占，就放进去
            if (h[t] == -1) {
                h[t] = get_key(x, y);
            }
            //如果这个点没被存入id中或者当前点的爆炸范围大于存入的点
            if (id[t] == 0 || cir[id[t]].r < r) {
                //就存入该点
                id[t] = i;
            }
        }

        //读入所有的火箭
        while (m-- > 0) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int r = scanner.nextInt();

            for (int i = x - r; i <= x + r; i++) {
                for (int j = y - r; j <= y + r; j++) {
                    if (sqr(i - x) + sqr(j - y) <= sqr(r)) {
                        //找该点的哈希值
                        int t = find(i, j);
                        //如果这个点存在，而且没有被搜过
                        if (id[t] != 0 && !st[t]) {
                            //那就搜一下这个点
                            dfs(i, j, cir[id[t]].r);
                        }
                    }
                }
            }
        }

        int res = 0;
        //枚举所有的雷 看看这个雷有没有被搜过(其实就是引爆)
        for (int i = 1; i <= n; i++) {
            if (st[find(cir[i].x, cir[i].y)]) {
                res++;
            }
        }

        System.out.println(res);
    }
}