题目大意：给定n个图形，每个图形可以是矩形或圆，，m次询问某个点在多少个图形内部
将点按横坐标排序
对于每个图形，二分找到x值满足要求的区间，对于区间内每个点暴力
时间复杂度O(n^2) 数据范围25W
果然像hwd说的一样计算几何题数据范围出的这么大就是作死么= =
#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 250250#define EPS 1e-7using namespace std;struct Point{double x,y;friend istream& operator >> (istream &_,Point &p){scanf("%lf%lf",&p.x,&p.y);return _;}bool operator < (const Point &p) const{return x<p.x;}friend double Distance(const Point &p1,const Point &p2){return sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) );}};struct _Point:Point{int id;friend istream& operator >> (istream &_,_Point &p){scanf("%lf%lf",&p.x,&p.y);return _;}}points[M];struct Rectangle{Point p1,p2;friend istream& operator >> (istream &_,Rectangle &r){cin>>r.p1>>r.p2;return _;}bool In_Range(const Point &p) const{return p1.y+EPS<p.y && p.y<p2.y-EPS;}};struct Circle{Point o;double r;friend istream& operator >> (istream &_,Circle &c){cin>>c.o;scanf("%lf",&c.r);return _;}bool In_Range(const Point &p) const{return Distance(o,p) < r-EPS;}};struct abcd{int type;union{public:Rectangle r;Circle c;};friend istream& operator >> (istream &_,abcd &a){char p[10];scanf("%s",p);if(p[0]=='r')a.type=1,cin>>a.r;elsea.type=2,cin>>a.c;return _;}bool In_Range(const Point &p){if(type==1)return r.In_Range(p);elsereturn c.In_Range(p);}}a[M];int n,m,ans[M];int main(){int i;cin>>n>>m;for(i=1;i<=n;i++)cin>>a[i];for(i=1;i<=m;i++)cin>>points[i],points[i].id=i;sort(points+1,points+m+1);for(i=1;i<=n;i++){Point l,r;if(a[i].type==1)l.x=a[i].r.p1.x+EPS,r.x=a[i].r.p2.x-EPS;elsel.x=a[i].c.o.x-a[i].c.r+EPS,r.x=a[i].c.o.x+a[i].c.r-EPS;_Point *_l=lower_bound(points+1,points+m+1,l);_Point *_r=lower_bound(points+1,points+m+1,r);for(;_l!=_r;_l++)if(a[i].In_Range(*_l))++ans[_l->id];}for(i=1;i<=m;i++)printf("%d\n",ans[i]);return 0;}
都成为命途中美丽的点缀，看天，看雪，安安静静，不言不语都是好风景。
