首页 > 其他 > 详细

poj2318

时间:2014-02-04 02:58:00      阅读:354      评论:0      收藏:0      [点我收藏+]
 
#include<iostream>
#include<cstdio>
#include<algorithm>
#define eps 1e-7
#define maxn 8000
using namespace std;
#define ll long long 
struct point{
   ll x,y;
};
int n,m;
ll x1,y1,x2,y2;
point a[maxn],b[maxn];
ll mul(ll a1,ll b1,ll a2,ll b2){
return a1*b2-a2*b1;
}
bool left(point x,point y){
if(mul(x.x-y.x,x.y-y1,y.y-y.x,y2-y1)>0)return 1;
else return 0;
}
int ans[maxn];
point b1[maxn],b2[maxn];
int bn1,bn2;
void solv(int al,int ar,int bl,int br){
if(al==ar){
    ans[al]=(br-bl+1);
return;
}
int mid=(al+ar)>>1;
bn1=0;
bn2=0;
for(int i=bl;i<=br;i++){
if(left(b[i],a[mid]))b1[++bn1]=b[i];
else b2[++bn2]=b[i];
}
for(int i=bl+1;i<=bl+bn1;i++){
   b[i-1]=b1[i-bl];
}
for(int i=bl+bn1;i<=br;i++){
   b[i]=b2[i-bl-bn1+1];
}
int k1=bl+bn1;
int k2=br;
solv(al,mid,bl,bl+bn1-1);
 
solv(mid+1,ar,k1,k2);
}
int main(){
while(1){
    scanf("%d",&n);
if(n==0)break;
scanf("%d%lld%lld%lld%lld",&m,&x1,&y1,&x2,&y2);
for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].x,&a[i].y);
for(int i=1;i<=m;i++)scanf("%lld%lld",&b[i].x,&b[i].y);
solv(1,n+1,1,m);
for(int i=1;i<=n+1;i++)printf("%d: %d\n",i-1,ans[i]);
printf("\n");
}
}

poj2318

原文:http://www.cnblogs.com/wangyucheng/p/3537616.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!