【BZOJ5008】方师傅的房子三角剖分

【BZOJ5008】方师傅的房子

Description

方师傅来到了一个二维平面。他站在原点上，觉得这里风景不错，就建了一个房子。这个房子是n个点的凸多边形，原点一定严格在凸多边形内部。有m个人也到了这个二维平面。现在你得到了m个人的坐标，你要判断这m个人中有多少人在房子内部。点在凸多边形边上或者内部都认为在房子里面。

Input

第一行一个数n，接下来n行，每行两个整数x，y。输入按照逆时针顺序输入一个凸包。

接下来一个数m，最后有m行，第一行两个整数 x，y，表示第一个人的坐标。

对于第i个询问(i>=2) ，输入两个数dx，dy。

如果上一个人在房子内部，x[i]=x[i-1]+dx,y[i]=y[i-1]+dy。否则x[i]=x[i-1]-dx,y[i]=y[i-1]-dy。

n <= 100000， m <= 200000，输入保证所有人的坐标，房屋的坐标都在[-1e9，1e9]之内。

Output

输出一个数，在房子内部人的个数。

Sample Input

4
-2 -2
2 -2
2 2
-2 2
3
5 5
4 4
0 3

Sample Output

题解：我们先随便选择一个点，然后对凸多边形进行三角剖分。这样每一个三角形管辖的范围都能看成是极角上的一段区间。在查询时我们二分找到对应点在那个三角形管辖的范围内，然后判断那个点是否在这个三角形里即可。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
int n,m;
int ans,lastans;
struct point
{
	int x,y;
	point() {}
	point(int a,int b) {x=a,y=b;}
	point operator - (const point &a) const {return point(x-a.x,y-a.y);}
	ll operator * (const point &a) const {return (ll)x*a.y-(ll)y*a.x;}
}p[100010],q;
inline char nc()
{
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd()
{
	int ret=0,f=1;	char gc=nc();
	while(!isdigit(gc))	{if(gc=='-')	f=-f;	gc=nc();}
	while(isdigit(gc))	ret=ret*10+(gc^'0'),gc=nc();
	return ret*f;
}
int main()
{
	n=rd();
	int i,l,r,mid;
	for(i=1;i<=n;i++)	p[i].x=rd(),p[i].y=rd();
	m=rd(),lastans=1;
	for(i=1;i<=m;i++)
	{
		q.x+=rd()*lastans,q.y+=rd()*lastans;
		if((p[2]-p[1])*(q-p[2])<0)	lastans=-1;
		else	if((p[n]-p[1])*(q-p[n])>0)	lastans=-1;
		else
		{
			l=2,r=n+1;
			while(l<r)
			{
				mid=(l+r)>>1;
				if((p[mid]-p[1])*(q-p[mid])>0)	l=mid+1;
				else	r=mid;
			}
			if((p[l]-p[l-1])*(q-p[l])>=0)	lastans=1,ans++;
			else	lastans=-1;
		}
	}
	printf("%d",ans);
	return 0;
}//4 -2 -2 2 -2 2 2 -2 2 3 5 5 4 4 0 3