将多边形按原点O做三角剖分，只考虑面积非0的三角形。
考虑三角形AOB时，只用判断在角AOB内（包括在射线OA和OB上）的绵羊是否在三角形OAB内
将绵羊按极角排序，扫描一遍即可，由于每只绵羊最多只可能在两个角内，故这一步的时间复杂度是线性的，算上排序，总时间复杂度为O(nlogn)
注意绵羊在原点的情况，要提前考虑
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
struct point
{
int x,y;
}a[100005],c[100005];
bool b[100005];
int ii;
int dj(int x1,int y1,int x2,int y2)
{
long long tmp=(long long)(x1)*x2+(long long)(y1)*y2;
if (tmp==0) return 0;
return tmp>0?1:-1;
}
int cj(int x1,int y1,int x2,int y2)
{
long long tmp=(long long)(x1)*y2-(long long)(x2)*y1;
if (tmp==0) return 0;
return tmp>0?1:-1;
}
bool check(const point &p)
{
int t=cj(a[ii].x,a[ii].y,p.x,p.y);
if (t>0) return true;
if (t<0) return false;
return dj(a[ii].x,a[ii].y,p.x,p.y)>0;
}
bool cmp(const point &p,const point &q)
{
bool b1=check(p),b2=check(q);
if (b1&&!b2) return true;
if (!b1&&b2) return false;
return cj(p.x,p.y,q.x,q.y)>0;
}
int main(void)
{
int res,n,m,i,j,k,t,u,g;
scanf("%d",&u);
while(u--)
{
res=0;
scanf("%d%d",&n,&t);
for(i=0;i<n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
for(m=0,i=0;i<t;i++)
{
scanf("%d%d",&c[m].x,&c[m].y);
if (c[m].x==0&&c[m].y==0)
res++;
else m++;
}
ii=0;
while(cj(a[ii].x,a[ii].y,a[(ii+1)%n].x,a[(ii+1)%n].y)==0)
ii++;
sort(c,c+m,cmp);
for(i=0;i<m;i++)
b[i]=true;
for(k=0,i=ii;i<n;i++)
{
j=i+1;
if (j==n)
j=0;
if (cj(a[i].x,a[i].y,a[j].x,a[j].y)==0)
continue;
while (cj(a[i].x,a[i].y,c[k].x,c[k].y)>=0
&&cj(c[k].x,c[k].y,a[j].x,a[j].y)>0)
{
if (b[k]&&cj(a[j].x-a[i].x,a[j].y-a[i].y,c[k].x-a[i].x,c[k].y-a[i].y)>=0)
{
res++;
b[k]=false;
}
k=(k+1)%m;
}
g=k;
while (cj(a[i].x,a[i].y,c[k].x,c[k].y)>=0
&&cj(c[k].x,c[k].y,a[j].x,a[j].y)>=0)
{
if (b[k]&&cj(a[j].x-a[i].x,a[j].y-a[i].y,c[k].x-a[i].x,c[k].y-a[i].y)>=0)
{
res++;
b[k]=false;
}
k=(k+1)%m;
}
k=g;
}
printf("%d\n",res);
}
return 0;
}
posted on 2010-10-01 21:23
zxb 阅读(116)
评论(0) 编辑 收藏 引用