POJ 2318(点集2分)

2013-01-26

POJ 2318(点集二分)Language:DefaultTOYSTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 813

POJ 2318(点集二分)
Language:TOYSTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 8137 Accepted: 3848

Description

在长方形 (x1,y1) (x2,y2) 中有n块板（保证与上下边相交），和m个点。现给出板和点的位置，求各区域点数、

POJ 2318(点集2分)

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 03 14 36 810 1015 301 52 12 85 540 107 94 10 0 10 100 020 2040 4060 6080 80 5 1015 1025 1035 1045 1055 1065 1075 1085 1095 100

Sample Output

0: 21: 12: 13: 14: 05: 10: 21: 22: 23: 24: 2

Hint

落在长方形边上的点也算.

Source

Rocky Mountain 2003

直接枚举点超时，

所以枚举中间那块板，二分查找（注意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) //Toystruct 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;}

热点排行

编程

POJ 2318(点集2分)