Description
汤姆是个好动的孩子,今天他突然对圆规和直尺来了兴趣。于是他开始在一张很大很大的白纸上画很多很多的矩形和圆。画着画着,一不小心将他的爆米花弄撒了,于是白纸上就多了好多好多的爆米花。汤姆发现爆米花在白纸上看起来就像一个个点,有些点落在矩形或圆内部,而有些则在外面。于是汤姆开始数每个点在多少个矩形或圆内部。毕竟汤姆还只是个孩子,而且点、矩形和圆又非常多。所以汤姆数了好一会都数不清,于是就向聪明的你求助了。你的任务是：在给定平面上N个图形(矩形或圆)以及M个点后，请你求出每个点在多少个矩形或圆内部(这里假设矩形的边都平行于坐标轴)。
Input
第一行为两个正整数N和M，其中N表示有多少个图形(矩形或圆)，M表示有多少个点。接下来的N行是对每个图形的描述，具体来说，第i+1行表示第i个图形。先是一个字母,若该字母为“r”，则表示该图形是一个矩形,这时后面将有4个实数x1,y1,x2,y2，表示该矩形的一对对角顶点的坐标分别为(x1,y1)和(x2,y2)；若该字母为“c”，则表示该图形是一个圆,这时后面将有3个实数x,y,r,表示该圆以(x,y)为圆心并以r为半径。最后M行是对每个点的描述，其中每行将有两个实数x,y,表示一个坐标为(x,y)的点。
Output
包含M行,每行是一个整数,其中第i行的整数表示第i个点在多少个图形内部(当某点在一个图形的边界上时，我们认为该点不在这个图形的内部)。
Sample
Input
3 4
r 1.015 0.750 5.000 4.000
c 6.000 5.000 2.020
r 6.500 7.200 7.800 9.200
3.500 2.500
4.995 3.990
2.300 8.150
6.900 8.000
Sample Output
1
2
0
1
好吧，写了很久，最后发现数组越界了（第20组n是20万，第18组就是25万，我只看了第20组数据.....谁叫他题目不写清楚，只能自己下数据了）
看了网上的C++程序，知道做法了
先将点按x坐标排序，再二分出有效区间即x坐标在矩形两个横坐标之间，或者在（x-r，x+r）之间的点，然后暴力是否被覆盖，统计答案
因为最开始那个问题，我还到处问人，去贴吧问，最后在我写完C++程序（照着网上的代码写）的时候发现n最大有25万，顿时崩溃了，改完就过了
1 const 2 eps=1e-7; 3 type 4 extended=double; 5 var 6 cx,cr,cy:array[0..250010]of extended; 7 lx,ly,rx,ry:array[0..250010]of extended; 8 ans,k:array[0..100010]of longint; 9 x,y:array[0..100010]of extended; 10 n,m,numr,numc:longint; 11 12 procedure swap(var x,y:extended); 13 var 14 t:extended; 15 begin 16 t:=x;x:=y;y:=t; 17 end; 18 19 procedure sort(l,r:longint); 20 var 21 i,j,t:longint; 22 z:extended; 23 begin 24 i:=l; 25 j:=r; 26 z:=x[(l+r)>>1]; 27 repeat 28 while z>x[i]+eps do 29 inc(i); 30 while x[j]>z+eps do 31 dec(j); 32 if i<=j then 33 begin 34 swap(x[i],x[j]); 35 swap(y[i],y[j]); 36 t:=k[i];k[i]:=k[j];k[j]:=t; 37 inc(i); 38 dec(j); 39 end; 40 until i>j; 41 if i<r then sort(i,r); 42 if j>l then sort(l,j); 43 end; 44 45 procedure init; 46 var 47 i:longint; 48 s:char; 49 begin 50 read(n,m); 51 for i:=1 to n do 52 begin 53 read(s); 54 while (s<>‘r‘)and(s<>‘c‘) do 55 read(s); 56 if s=‘r‘ then 57 begin 58 inc(numr); 59 read(lx[numr],ly[numr],rx[numr],ry[numr]); 60 if lx[numr]>rx[numr] then swap(lx[numr],rx[numr]); 61 if ly[numr]>ry[numr] then swap(ly[numr],ry[numr]); 62 end 63 else 64 begin 65 inc(numc); 66 read(cx[numc],cy[numc],cr[numc]); 67 end; 68 end; 69 for i:=1 to m do 70 read(x[i],y[i]); 71 for i:=1 to m do 72 k[i]:=i; 73 sort(1,m); 74 end; 75 76 procedure work; 77 var 78 i,j,ll,rr,left,right,mid:longint; 79 begin 80 for i:=1 to numc do 81 begin 82 left:=1;right:=m; 83 while left<right do 84 begin 85 mid:=(left+right)>>1; 86 if x[mid]>cx[i]-cr[i] then right:=mid 87 else left:=mid+1; 88 end; 89 ll:=left; 90 left:=1;right:=m; 91 while left<right do 92 begin 93 mid:=(left+right+1)>>1; 94 if cx[i]+cr[i]>x[mid] then left:=mid 95 else right:=mid-1; 96 end; 97 rr:=right; 98 for j:=ll to rr do 99 if sqr(cr[i])-eps>sqr(x[j]-cx[i])+sqr(y[j]-cy[i]) then inc(ans[k[j]]); 100 end; 101 for i:=1 to numr do 102 begin 103 left:=1;right:=m; 104 while left<right do 105 begin 106 mid:=(left+right)>>1; 107 if x[mid]>lx[i] then right:=mid 108 else left:=mid+1; 109 end; 110 ll:=left; 111 left:=1;right:=m; 112 while left<right do 113 begin 114 mid:=(left+right+1)>>1; 115 if rx[i]>x[mid] then left:=mid 116 else right:=mid-1; 117 end; 118 rr:=right; 119 for j:=ll to rr do 120 if (y[j]>ly[i]+eps)and(ry[i]>y[j]+eps)and(x[j]>lx[i]+eps)and(rx[i]>x[j]+eps) then inc(ans[k[j]]); 121 end; 122 for i:=1 to m do 123 writeln(ans[i]); 124 end; 125 126 begin 127 init; 128 work; 129 end.
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 5 typedef double ld; 6 7 const int maxn=250010; 8 const int maxm=10010; 9 const ld eps=1e-7; 10 11 int n,m,ans[maxm]; 12 13 struct REC 14 { 15 ld lx,ly,rx,ry; 16 }rec[maxn]; 17 int numr; 18 19 struct CIR 20 { 21 ld x,y,r; 22 }cir[maxn]; 23 int numc; 24 25 struct point 26 { 27 ld x,y; 28 int k; 29 }d[maxm]; 30 31 int operator < (const point & a,const point & b) 32 { 33 return a.x<b.x; 34 } 35 36 int main() 37 { 38 int i,j; 39 scanf("%d%d",&n,&m); 40 char s; 41 for(i=1;i<=n;++i) 42 { 43 scanf("%s",&s); 44 if(s==‘r‘) 45 { 46 ++numr; 47 scanf("%lf%lf%lf%lf",&rec[numr].lx,&rec[numr].ly,&rec[numr].rx,&rec[numr].ry); 48 if(rec[numr].lx>rec[numr].rx) 49 swap(rec[numr].lx,rec[numr].rx); 50 if(rec[numr].ly>rec[numr].ry) 51 swap(rec[numr].ly,rec[numr].ry); 52 } 53 else 54 { 55 ++numc; 56 scanf("%lf%lf%lf",&cir[numc].x,&cir[numc].y,&cir[numc].r); 57 } 58 } 59 for(i=1;i<=m;++i) 60 { 61 scanf("%lf%lf",&d[i].x,&d[i].y); 62 d[i].k=i; 63 } 64 sort(d+1,d+m+1); 65 int left,right,ll,rr,mid; 66 for(i=1;i<=numr;++i) 67 { 68 left=1,right=m; 69 while(left<right) 70 { 71 mid=(left+right)/2; 72 if(d[mid].x>rec[i].lx)right=mid; 73 else left=mid+1; 74 } 75 ll=left; 76 left=1;right=m; 77 while(left<right) 78 { 79 mid=(left+right+1)/2; 80 if(d[mid].x<rec[i].rx)left=mid; 81 else right=mid-1; 82 } 83 rr=right; 84 for(j=ll;j<=rr;++j) 85 if((d[j].x>rec[i].lx+eps)&(rec[i].rx>d[j].x+eps)&(d[j].y>rec[i].ly+eps)&(rec[i].ry>d[j].y+eps)) 86 ++ans[d[j].k]; 87 } 88 for(i=1;i<=numc;++i) 89 { 90 left=1;right=m; 91 while(left<right) 92 { 93 mid=(left+right)/2; 94 if(d[mid].x>cir[i].x-cir[i].r)right=mid; 95 else left=mid+1; 96 } 97 ll=left; 98 left=1;right=m; 99 while(left<right) 100 { 101 mid=(left+right+1)/2; 102 if(cir[i].x+cir[i].r>d[mid].x)left=mid; 103 else right=mid-1; 104 } 105 rr=right; 106 for(j=ll;j<=rr;++j) 107 if(cir[i].r*cir[i].r>(d[j].x-cir[i].x)*(d[j].x-cir[i].x)+(d[j].y-cir[i].y)*(d[j].y-cir[i].y)) 108 ++ans[d[j].k]; 109 } 110 for(i=1;i<=m;++i) 111 printf("%d\n",ans[i]); 112 return 0; 113 }
1199: [HNOI2005]汤姆的游戏 - BZOJ,布布扣,bubuko.com
原文：http://www.cnblogs.com/Randolph87/p/3594524.html
