//計算幾何第一題
//學習了叉積和利用叉積判斷左右位置關系
//叉積+二分
//延續了這兩天比賽的PE黑手
#include<iostream>
using namespace std;
#define MAXN 5000+1
#define eps 1e-8
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
struct point
{int x,y;};
struct line{point a,b;};
int ans[MAXN];
point toys[MAXN];
line board[MAXN];
double xmult(point p0,point p1,point p2){//叉積，囧
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int main()
{
int n,m,x1,y1,x2,y2,u1,u2,i;
bool flag=false;
while(scanf("%d",&n)!=EOF && n )
{
if(flag) printf("\n");
memset(ans,0,sizeof(ans));
scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
for(i=0;i<n;i++)
{
scanf("%d%d",&u1,&u2);
board[i].a.x=u1;
board[i].a.y=y1;
board[i].b.x=u2;
board[i].b.y=y2;
}
board[n].a.x=x2;
board[n].a.y=y1;
board[n].b.x=x2;
board[n].b.y=y2;
for(i=0;i<m;i++)
{
scanf("%d%d",&(toys[i].x),&(toys[i].y));
int low=0,hig=n,mid;
while(low+1<hig)
{
mid=(low+hig)>>1;
double res=xmult(board[mid].a,board[mid].b,toys[i]);
//if(res>0)
if(res>0) low=mid;
else hig=mid;
}
if(xmult(board[low].a,board[low].b,toys[i])<0) ans[low]++;
else ans[low+1]++;
}
for(i=0;i<=n;i++)
{
printf("%d: %d\n",i,ans[i]);
}
flag=true;
}
return 0;
}posted on 2009-10-04 12:14
wyiu 閱讀(153)
評論(0) 編輯 收藏 引用 所屬分類:
POJ