题解：CF33D Knights

· · 题解

题目传送门

题意

给出 n 个坐标，给定 m 个互不交叉的圆，给出 k 个询问，每次询问两个坐标的连线与圆有多少个交点。

思路

注意到 n 和 m 的范围都很小，所以我们可以枚举所有圆和坐标，定义 f_{i,j} 为第 i 个坐标是否被第 j 个圆包含。

每次询问，我们也是枚举所有的圆，如果第 i 个圆，包含了第一个坐标，但没有包含第二个坐标，或者包含了第二个坐标，没有包含第一个坐标的话，答案就加一。

即 f_{a,i}\ne f_{b,i} 时，答案加一。

复杂度 O(mk)。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010101;
ll n,m,k,x[N],y[N],r[N],dx[N],dy[N],a,b,ans,f[1010][1010];
int main(){
    ios::sync_with_stdio(false);
    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]>>dx[i]>>dy[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ll xx=x[i]-dx[j],yy=y[i]-dy[j];
            if(xx*xx+yy*yy<=r[j]*r[j])f[i][j]=1;
        }
    }
    while(k--){
        ans=0;
        cin>>a>>b;
        for(int i=1;i<=m;i++){
            if(f[a][i]!=f[b][i])ans++;
        }
        cout<<ans<<"\n";
    }
    return 0;
}