【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

房子