http://www.lydsy.com/JudgeOnline/problem.php?id=1199
求出圆x的范围
把要判断的点按x从小到大排序
枚举图形
二分出x满足这个图形的一段区间
枚举这段区间内的每个点
圆判断到圆心的距离
矩形判断y
代码不是我的~~~
#include<bits/stdc++.h>
#define N 1000010
using namespace std;
const double eps=1e-;
struct node
{
double x1,x2,y1,y2;
double x,y,r;
char c;
bool friend operator < (node a,node b)
{
return a.x1<b.x1;
}
}a[N];
char s[];
int out[N];
struct point
{
double x,y;
int num;
}e[N];
int n,m;
double sqr(double x)
{
return x*x;
}
bool pd(double x1,double y1,double x,double y,double r)
{
return sqr(x-x1)+sqr(y-y1)<sqr(r);
}
bool cmp(point a,point b)
{
return a.x<b.x;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%s",s+);
if(s[]=='r')
{
scanf("%lf%lf%lf%lf",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
if(a[i].x1>a[i].x2) swap(a[i].x1,a[i].x2),swap(a[i].y1,a[i].y2);
a[i].c=s[];
}
else
{
scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r);
a[i].x1=a[i].x-a[i].r;a[i].x2=a[i].x+a[i].r;
a[i].c=s[];
}
}
for(int i=;i<=m;i++) scanf("%lf%lf",&e[i].x,&e[i].y),e[i].num=i;
sort(e+,e+m+,cmp);
for(int i=;i<=n;i++)
{
int ll=-,rr=-;
int l=,r=m;
while(l<=r)
{
int mid=l+r>>;
if(e[mid].x>a[i].x1)
{
ll=mid;
r=mid-;
}
else l=mid+;
}
l=,r=m;
while(l<=r)
{
int mid=l+r>>;
if(e[mid].x<a[i].x2)
{
rr=mid;
l=mid+;
}
else r=mid-;
}
if(ll==- || rr==-) continue;
for(int j=ll;j<=rr;j++)
{
if(a[i].c=='c')
{
if(pd(e[j].x,e[j].y,a[i].x,a[i].y,a[i].r)) out[e[j].num]++;
}
else
{
if(e[j].y<a[i].y2&&e[j].y>a[i].y1) out[e[j].num]++;
}
}
}
for(int i=;i<=m;i++)
cout<<out[i]<<"\n";
return ;
}