Language: TOYS Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 8137 Accepted: 3848 Description 在長方形 (x1,y1) (x2,y2) 中有n塊板（保證與上下邊相交），和m個點。 現給出板和點的位置，求各區域點數、 Input 多組數據.每組數據開頭為 n m x1 y1 x2 y2. n (0 < n <= 5000) m (0 < m <= 5000). (x1,y1)為左上角坐標 , (x2,y2)為右下角坐標. 接下來 n 行有2個數 Ui Li,表示第i塊板為 (Ui,y1) (Li,y2). （保證兩兩不交，且板從左至右給出）. 接下來m 行為點的坐標 Xj Yj （保證不在板上） 數據以 0 結束. Output 每組數據給出各區域點數（最左邊區域編號0） 區域編號: 點數 …(區域編號0→n) 請按這個格式輸出。 不同組數據間輸出一空行。 Sample Input 5 6 0 10 60 0 3 1 4 3 6 8 10 10 15 30 1 5 2 1 2 8 5 5 40 10 7 9 4 10 0 10 100 0 20 20 40 40 60 60 80 80 5 10 15 10 25 10 35 10 45 10 55 10 65 10 75 10 85 10 95 10 0 Sample Output 0: 2 1: 1 2: 1 3: 1 4: 0 5: 1 0: 2 1: 2 2: 2 3: 2 4: 2 Hint 落在長方形邊上的點也算. Source Rocky Mountain 2003 直接枚舉點超時， 所以枚舉中間那塊板，二分查找（注意Qsort性質,[1, i-1] 和 [ j+1,n]即為所求范圍） 但是由於中間那塊板並不“計入點集”，所以 i 和 j 可能 越界，要特判。 由於用int會乘越界（這題沒給范圍），所以穩妥的用double. [cpp] #include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<iostream> #include<algorithm> #include<functional> using namespace std; #define MAXN (5000+10) //Board #define MAXM (5000+10) //Toy struct P { double x,y; P(){} P(int _x,int _y):x(_x),y(_y){} friend istream& operator>>(istream& cin,P &a){cin>>a.x>>a.y;return cin; } }a[MAXM]; struct V { double x,y; P s; V(){} V(P a,P b):x(b.x-a.x),y(b.y-a.y),s(a){} friend int operator*(const V a,const V b) { return a.x*b.y-a.y*b.x; } }c[MAXN]; int n,m,x1,y1,x2,y2; void binary(int L,int R,int l,int r) { if (R-L==1) { cout<<L<<": "<<r-l+1<<endl; return; } int i=l,j=r,m=(l+r)>>1; V &M=c[(L+R)>>1]; do { while (i<=r&&V(M.s,a[i])*M<0) i++; while (j>=l&&V(M.s,a[j])*M>0) j--; if (i<=j) {swap(a[i],a[j]);i++;j--; } }while (i<=j); i--;j++; binary(L,(L+R)>>1,l,i); binary((L+R)>>1,R,j,r); } int main() { // freopen("poj2318.in","r",stdin); scanf("%d%d",&n,&m); while (1) { cin>>x1>>y2>>x2>>y1; for (int i=1;i<=n;i++) { int u,l; cin>>u>>l; c[i]=V(P(l,y1),P(u,y2)); } c[0]=V(P(x1,y1),P(x1,y2));c[n+1]=V(P(x2,y1),P(x2,y2)); for (int i=1;i<=m;i++) cin>>a[i]; binary(0,n+1,1,m); if (scanf("%d%d",&n,&m)==2) cout<<endl; else break; } return 0; }
