点的内包：判断点是否在多边形内。
输入 一个多边形点的序列 问题数 各个问题的点的信息 输出 2代表在圈内 1代表在圈上 0代表在圈外只要检查一p为端点且平行于x的射线与多边形g的边的相交次数，我们就能判断给定的点p是否内包与多边形g。对于构成多边形各边的线段
设与分别为向量a和向量b。点p是否位于上可通过ccw的方法检验，即检验a和b是否在同一直线上且方向相反。如果a和b外积大小为0且内积小于等于0，则点p位于上。
接着我们调整a，b的值使y小的为a，大的为b。在这个状态下，如果a和b外积的大小为正且a，b位于射线两侧，则可确定相交。
这里要注意设置边界条件，避免射线与端点相交时对结果造成影响。
//点的内包 int contains(Polygon g,Point p){ int n=g.size(); bool x=false; for(int i=0;i<n;i++){ Vector a=g[i]-p,b=g[(i+1)%n]-p; if(abs(cross(a,b))<EPS&&dot(a,b)<EPS) return 1; if(a.y>b.y) swap(a,b); if(a.y<EPS&&b.y>EPS&&cross(a,b)>EPS) x=!x; } return (x?2:0); }凸包：包含点集合P中所有点的最小凸多边形。
输入 一系列的点序列 输出 逆时针输出凸包人们已经研究出了数个求凸包的算法。这里我们将要学习的是相对容易掌握的安德鲁算法(Andrew's Algorithm)。
将给定集合的点按照x坐标升序排列。x相同时按照y坐标升序排列。按照下述流程创建凸包的上部 将顺序后的点按照x坐标从小到大的顺序加入凸包U。如果新加入的点使得U不再是多边形，则逆序删除之前加入的U的点，直到重新成为凸多边形。我们利用准备加入的点S[i]与在U中的倒数两个点来判断。如图所示过程。按照下述流程创建凸包的下部 将顺序后的点按照x坐标从大到小的顺序加入凸包U。如果新加入的点使得L不再是多边形，则逆序删除之前加入的L的点，直到重新成为凸多边形。我们利用准备加入的点S[i]与在L中的倒数两个点来判断。如图所示过程。 Polygon andrewScan(Polygon s){ Polygon u,l; if(s.size()<3) return s; //以x，y为基准升序排序 sort(s.begin(),s.end()); //将x的最小两个点放入 u.push_back(s[0]); u.push_back(s[1]); //将最大的两个点放入 l.push_back(s[s.size()-1]); l.push_back(s[s.size()-2]); //构建凸包上部 for(int i=2;i<s.size();i++){ for(int n=u.size();n>=2&&ccw(s[i],u[n-1],u[n-2])==CLOCKWISE;n--){ u.pop_back(); } u.push_back(s[i]); } //构建凸包下部 for(int i=s.size()-3;i>=0;i--){ for(int n=l.size();n>=2&&ccw(s[i],l[n-1],l[n-2])==CLOCKWISE;n--){ l.pop_back(); } l.push_back(s[i]); } //顺时针方向生成凸包的点的序列 reverse(l.begin(),l.end()); for(int i=u.size()-2;i>=1;i--) l.push_back(u[i]); return l; }线段相交问题
给出n条平行于x轴或者y轴的线段，请输出其交点数
基本思路:
与轴平行的线段相交问题(曼哈顿几何)可以通过平面扫描(sweep)高效求解。平面扫描算法的思路是将一条与x轴(或者y轴)平行的直线向上(向右)平行移动，在移动过程中寻找交点。这条直线称为扫描线。
扫描线并不是按照固定的间隔逐行扫描，而是在每次遇到线段上的端点时停止移动，然后检查该位置上的线段交点数。因此我们需要先将输入的线段端点按照y值排序，让扫描线向y轴正方向移动。
再扫描过程中，算法会将扫描线穿过的垂直线段(与y轴平行)临时记录下来，等到扫描线与水平线段(平行于x轴)重叠时，检查在水平线段范围内的交点数。
为提高效率，我们可以应用二叉搜索树来保存扫描线穿过的垂直线段。
#define BOTTOM 0 #define LEFT 1 #define RIGHT 2 #define TOP 3 class EndPoint{ public: Point p; int seg,st;//输入线段的ID和端点种类 EndPoint(){ } EndPoint(Point p,int seg,int st):p(p),seg(seg),st(st){ } bool operator < (const EndPoint &ep) const{ //按y坐标升序排列 if(p.y==ep.p.y){ return st<ep.st; } else{ return p.y<ep.p.y; } } }; EndPoint EP[2*100000];//端点列表 //直线相交问题 int manhattanIntersection(vector<Segment> S){ int n=S.size(); for(int i=0,k=0;i<n;i++){ //调整端点p1,p2,保证左小右大 if(S[i].p1.y==S[i].p2.y){ if(S[i].p1.x>S[i].p2.x) swap(S[i].p1,S[i].p2); }else if(S[i].p1.y>S[i].p2.y) swap(S[i].p1,S[i].p2); if(S[i].p1.y==S[i].p2.y){ EP[k++]=EndPoint(S[i].p1,i,LEFT); EP[k++]=EndPoint(S[i].p2,i,RIGHT); } else{ EP[k++]=EndPoint(S[i].p1,i,BOTTOM); EP[k++]=EndPoint(S[i].p2,i,TOP); } } sort(EP,EP+(2*n)); set<int>BT; BT.insert(1000000001); int cnt=0; for(int i=0;i<2*n;i++){ if(EP[i].st==TOP) BT.erase(EP[i].p.x);//删除上端点 else if(EP[i].st==BOTTOM) BT.insert(EP[i].p.x); else if(EP[i].st==LEFT){ set<int>::iterator b = BT.lower_bound(S[EP[i].seg].p1.x); set<int>::iterator e = BT.upper_bound(S[EP[i].seg].p2.x); cnt+=distance(b,e); } } return cnt; }
