题解：CF33D Knights

题目传送门

题意

给出

n

个坐标，给定

m

个互不交叉的圆，给出

k

个询问，每次询问两个坐标的连线与圆有多少个交点。

思路

注意到

n

和

m

的范围都很小，所以我们可以枚举所有圆和坐标，定义

f_{i,j}

为第

i

个坐标是否被第

j

个圆包含。

每次询问，我们也是枚举所有的圆，如果第

i

个圆，包含了第一个坐标，但没有包含第二个坐标，或者包含了第二个坐标，没有包含第一个坐标的话，答案就加一。

即

f_{a,i}\ne f_{b,i}

时，答案加一。

复杂度

O(mk)

。

代码

CPP

#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;
}

文章操作

题目传送门

题意

思路

代码

相关推荐

评论

题解：CF33D Knights