计算几何终于开坑了。。。
叉积+二分。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 5050
using namespace std;
struct point
{
int x,y;
point (int x,int y):x(x),y(y) {}
point () {}
friend point operator-(point x,point y)
{
return point(x.x-y.x,x.y-y.y);
}
}p[maxn];
struct line
{
point x,dt;
line (point x,point dt):x(x),dt(dt) {}
line () {}
friend int operator*(line x,line y)
{
return x.dt.x*y.dt.y-y.dt.x*x.dt.y;
}
}l[maxn];
int n,m,cnt[maxn],x1,y1,x2,y2,x,y;
bool check(int xs) {return (line(l[xs].x,point(x,y)-l[xs].x)*l[xs])>=;}
int ask()
{
int l=,r=n,ans=-;
while (l<=r)
{
int mid=(l+r)>>;
if (check(mid)) {ans=mid;l=mid+;}
else r=mid-;
}
return ans;
}
int main()
{
for (;;)
{
scanf("%d",&n);if (!n) break;scanf("%d",&m);
scanf("%d%d%d%d",&x1,&y2,&x2,&y1);
memset(cnt,,sizeof(cnt));
l[]=line(point(x1,y1),point(,y2-y1));
for (int i=;i<=n;i++)
{
scanf("%d%d",&x,&y);
l[i]=line(point(y,y1),point(x-y,y2-y1));
}
l[n+]=line(point(x2,y1),point(,y2-y1));
for (int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
cnt[ask()]++;
}
for (int i=;i<=n;i++) printf("%d: %d\n",i,cnt[i]);
printf("\n");
}
return ;
}