题目描述

在一个二维平面上有 n 个点和 m 个圆。

点的编号为 1∼n。

不存在某个点恰好在某个圆的边上的情况。

任意两个圆之间没有公共点。

现在，请你回答 k 个询问。

每个询问给定两个点 ai,bi，并请你回答从点 ai 出发沿任意连续路径到达点 bi，至少需要穿过多少个圆。

输入格式
第一行包含三个整数 n,m,k。

接下来 n 行，其中第 i 行包含两个整数 xi,yi，表示点 i 的坐标为 (xi,yi)。注意，点的位置可以重合。

再接下来 m 行，其中第 i 行包含三个整数 ri,cxi,cyi，表示第 i 个圆的半径为 ri，圆心坐标为 (cxi,cyi)。

最后 k 行，每行包含两个整数 ai,bi，表示一个询问。注意，ai 可以等于 bi。

输出格式
共 k 行，第 i 行输出第 i 个询问的答案，即最少需要穿过的圆的数量。

数据范围
前三个测试点满足 1≤n,m,k≤10。
所有测试点满足 1≤n,m≤1000，1≤k≤105，−109≤xi,yi,cxi,cyi≤109，1≤ri≤109，1≤ai,bi≤n。

勾股定理+位运算

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int n,m,k,x[1111],y[1111],a,b,r[1111],cx[1111],cy[1111],s[1111][1111];
bool check(int xx, int yy) 
{
    double dx = x[xx] - cx[yy];
    double dy = y[xx] - cy[yy];
    return sqrt(dx * dx + dy * dy) < r[yy]+1e-9;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    for(int i=1;i<=m;i++){
        cin>>r[i]>>cx[i]>>cy[i];
    }
    bitset<1111> h[1111];
    for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= m; j ++)
    if(check(i, j)) h[i].set(j);
    for(int i=1;i<=k;i++){
        cin>>a>>b;
        auto t = h[a] ^ h[b];
        cout << t.count() << endl;
    }
}