POJ 2398(二分点集)


 
Language:
Toy Storage
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
每组数据给出同点数的区域数
点数: 区域数
…(点数1→n，区域数为0不输出)
 
请按这个格式输出。
每组数据开头输出“Box”。 
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
 
基本同POJ 2318
 
[cpp]  
#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cctype>  
#include<iostream>  
#include<algorithm>  
#include<functional>  
using namespace std;  
#define MAXN (1000+10) //Board  
#define MAXM (1000+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,f[MAXM];  
int cmp(V a,V b)  
{  
    return a.s.x<b.s.x;  
}  
void binary(int L,int R,int l,int r)  
{  
    if (R-L==1)  
    {  
        f[r-l+1]++;  
        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("poj2398.in","r",stdin);  
      
    while (scanf("%d%d",&n,&m)==2)  
    {  
        cout<<"Box\n";  
        memset(f,0,sizeof(f));  
        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));    
        sort(c+1,c+1+n,cmp);  
        for (int i=1;i<=m;i++) cin>>a[i];  
        binary(0,n+1,1,m);    
        for (int i=1;i<=m;i++)  
            if (f[i]) cout<<i<<": "<<f[i]<<endl;  
    }  
    return 0;  
}

补充：web前端 , JavaScript ,