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
-2 -2
2 -2
2 2
-2 2
3
5 5
4 4
0 3
Sample Output
1
Solution
一个一个找显然是不行的
我们把第一个点作为基点，向其他所有点连边，这样就把凸多边形变成了若干个三角形（伪三角剖分。。）
因为给出的数据是已经排好序了的，所以对于每一个询问，我们先二分找到当前点属于哪一个三角形范围之内
之后就只要判断点是否在三角形之内就行了
还要注意一些小细节，比如凸多边形上1号点和n号点之间的范围，还有精度问题
最开始我写的是atan2的极角排序，后来怎么调也没过，现在还不知道是什么原因
后来对于每一凸包上的每一个点i，我们判断询问的点x是否在1点与i点连边的“左”方，一样可以达到效果
#include<bits/stdc++.h> #define ll long long const int MAXN=100000+10,MAXM=200000+10; int n,m,x[MAXM],y[MAXM],ans,pre; struct node{ int x,y; double angle; inline bool operator < (const node &A) const { return angle<A.angle; }; inline node operator - (const node &A) const { node tmp; tmp.x=x-A.x; tmp.y=y-A.y; return tmp; }; }; node point[MAXN]; template<typename T> inline void read(T &x) { T data=0,w=1; char ch=0; while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')w=-1,ch=getchar(); while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar(); x=data*w; } template<typename T> inline void write(T x,char c=' ') { if(x<0)putchar('-'),x=-x; if(x>9)write(x/10); putchar(x%10+'0'); if(c!=' ')putchar(c); } template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);} template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);} template<typename T> inline T min(T x,T y){return x<y?x:y;} template<typename T> inline T max(T x,T y){return x>y?x:y;} inline ll cross(node a,node b) { return (ll)a.x*(ll)b.y-(ll)b.x*(ll)a.y; } inline bool check(int dx,int dy) { node q; q.x=dx;q.y=dy; if(cross(point[2]-point[1],q-point[2])<0)return false; if(cross(point[n]-point[1],q-point[n])>0)return false; int l=2,r=n+1; while(l<r) { int mid=(l+r)>>1; if(cross(point[mid]-point[1],q-point[mid])>0)l=mid+1; else r=mid; } if(cross(point[l]-point[l-1],q-point[l])>=0)return true; else return false; } int main() { read(n); for(register int i=1;i<=n;++i)read(point[i].x),read(point[i].y); read(m); for(register int i=1;i<=m;++i) { read(x[i]);read(y[i]); if(i==1); else if(pre)x[i]=x[i-1]+x[i],y[i]=y[i-1]+y[i]; else x[i]=x[i-1]-x[i],y[i]=y[i-1]-y[i]; if(check(x[i],y[i]))ans++,pre=1; else pre=0; } write(ans,' '); return 0; }