給定n個(gè)點(diǎn)的坐標(biāo)
圓1的坐標(biāo) 圓2的坐標(biāo) 詢問(wèn)次數(shù)
圓1的半徑 圓2的半徑
問(wèn)：對(duì)于每個(gè)詢問(wèn)，求出（不在圓上的點(diǎn) - 在2圓重合 部分的點(diǎn) ） //注意當(dāng)答案<0 輸出0托福答案
思路：首先對(duì)題意轉(zhuǎn)化，可以看成是求 n - （在圓1上的點(diǎn)）-（在圓2上的點(diǎn)）
因?yàn)樗悬c(diǎn)是固定的，所以 （在圓1的點(diǎn)） => DIS（ 點(diǎn)，圓心1） <= R1
只要求出所有滿足上述不等式點(diǎn)的個(gè)數(shù)即可
把所有點(diǎn)按 （到圓心1的距離）小到大排序，存在p1數(shù)組中，再把p1中有相同dis的點(diǎn)去重后存在k1數(shù)組中，k1.num 就表示 距離<=k1.dis的點(diǎn)有 k1.num個(gè)托福改分
然后二分找到k1.dis <= R1 的最大的k1.num ,就是（在圓1上的點(diǎn)）
對(duì)圓2上的點(diǎn)相同操作
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 2000000
#define N 200200
using namespace std;
struct node{
int x,y;
int dis;
bool operator<（const node& a）const {return a.dis>dis;}
}p1[N],p2[N],r1,r2;
struct kk{
int dis,num;
}k1[N],k2[N];
int kn1,kn2;
int R1,R2,sum1,sum2,n;
int DIS（node a,node b）{return （a.x-b.x）*（a.x-b.x）+（a.y-b.y）*（a.y-b.y）；}
int erfen1（int l,int r,int d）{
if（l==r-1 && k1[l].dis<=d && k1[r].dis>d ）
return k1[l].num;
int mid=（l+r）》1;
if（k1[mid].dis>d）return erfen1（l,mid,d）；
if（k1[mid].dis
if（k1[mid].dis==d）return k1[mid].num;
}
int erfen2（int l,int r,int d）{
if（l==r-1 && k2[l].dis<=d && k2[r].dis>d ）
return k2[l].num;
int mid=（l+r）》1;
if（k2[mid].dis>d）return erfen2（l,mid,d）；
if（k2[mid].dis
if（k2[mid].dis==d）return k2[mid].num;
}
void quchong（）{//p數(shù)組去重得到k數(shù)組
int i;
for（i=1;i<=n;i++）
{
if（p1[i].dis==p1[i-1].dis）k1[kn1].num++;
else
{
kn1++;
k1[kn1].dis=p1[i].dis;
k1[kn1].num=1+k1[kn1-1].num;
}
if（p2[i].dis==p2[i-1].dis）k2[kn2].num++;
else
{
kn2++;
k2[kn2].dis=p2[i].dis;
k2[kn2].num=1+k2[kn2-1].num;
}
}
}
int main（）{
int i,j,query,Cas=1;
p1[0].dis=p2[0].dis=-1; //去重邊界
while（scanf（"%d",&n），n）{
for（i=1;i<=n;i++）scanf（"%d%d",&p1[i].x,&p1[i].y），p2[i]=p1[i];
scanf（"%d %d %d %d %d",&r1.x,&r1.y,&r2.x,&r2.y,&query）；
for（i=1;i<=n;i++）
p1[i].dis=DIS（p1[i],r1）， p2[i].dis=DIS（p2[i],r2）；
sort（p1+1,p1+n+1）；
sort（p2+1,p2+n+1）；
kn1=kn2=0;
quchong（）；
k1[0].dis=k2[0].dis=-1; //二分需要的邊界條件
k1[0].num=k2[0].num=0;
k1[kn1+1].dis=k2[kn2+1].dis=inf; //二分需要的邊界條件
printf（"Case %d:\n",Cas++）；
while（query--）
{
scanf（"%d %d",&R1,&R2）；
sum1=erfen1（1,kn1,R1*R1）；
sum2=erfen2（1,kn2,R2*R2）；
int ans=n-sum1-sum2;
if（ans<0）ans=0;
printf（"%d\n",ans）；
}
}
return 0;
}
/*
11
95 75
27 6
93 5
124 13
34 49
65 61
81 49
77 33
110 50
91 22
110 25
57 42 97 36 2
31 25
25 25
15
1 1
2 2
3 3
4 4
5 5
10 5
15 5
1 0
2 0
3 0
4 0
5 0
6 0
10 0
20000 20000
10 0 5 5 2
7 1
8 1
ans:
2
2
8
3
*/