POJ 2318(点集二分)

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

直接枚举点超时,

所以枚举中间那块板,二分查找(注意Qsort性质,[1, i-1]  和 [ j+1,n]即为所求范围)

但是由于中间那块板并不“计入点集”,所以 i 和 j 可能 越界,要特判。

由于用int会乘越界(这题没给范围),所以稳妥的用double.



#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;
}