把点集凸包化Granham-Scan算法(使用水平序)

1、把点集凸包化Granham-Scan算法（使用水平序）#include#include#include#includeusing nameaace std;const int M=100000+5;struct Pointdouble x,y; pM;double dis(Point A,Point B)return sqrt(B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y);bool cmp(Point a,Point b)if (a.xb.x) return false;if (a.yb.y) return true;return false;double Xd

2、et(Point A,Point B,Point C)double x1,x2,y1,y2;x1=B.x-A.x;y1=B.y-A.y;x2=C.x-A.x;y2=C.y-A.y;return x1*y2-x2*y1; /大于0在左手边，逆时针bool boM;Point ppM;int stackM; /from 1 to tvoid Gram_Scan(Point *p,int &n) /p从1-n,把点集土包化 n*log(n);int i,t;sort(p+1,p+1+n,cmp);for(t=0,i=1;i1 & pi.x=pi-1.x & pi.y=pi-1.y) continue

3、;p+t=pi;n=t;t=0;memset(bo+1,true,n*sizeof(bo0);if (n0)stack+t=1;bostackt=false;if (n1)stack+t=2;bostackt=false;if (n2)for(i=3;i=0) stack+t=i,boi=false;elsewhile(t=2& Xdet(pstackt-1,pstackt,pi)=1;i-)if (boi & Xdet(pstackt-1,pstackt,pi)=0) stack+t=i,boi=false;elsewhile(t=2&Xdet(pstackt-1,pstackt,pi)0)

4、 bostackt=true,t-;stack+t=i;bostackt=false;t-;for(i=1;i=t;i+)ppi=pstacki;memcpy(p+1,pp+1,t*sizeof(Point);n=t;求凸点集的面积double area(Point *p,int n)double sum=0;int i;pn+1=p1;for(i=1;i0?(x):-(x)EPS)struct Pointdouble x,y; pM;struct LINESEGPoint st,ed;struct LINEdouble a,b,c;double dist(Point a,Point b)re

5、turn sqrt(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);double multiply(Point a,Point b,Point c)return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);double dotmultiply(Point a,Point b,Point c)return (a.x-c.x)*(b.x-c.x)+(a.y-c.y)*(b.y-c.y);bool online(LINESEG L,Point q) LINE makeline(Point p1,Point p2)LINE tl;tl.

6、a=p2.y-p1.y;tl.b=p1.x-p2.x;if (tl.ay?x:y;inline double MIN(double x,double y)return x=0& multiply(u.st,v.ed,v.st)*multiply(v.ed,u.ed,v.st)=0;bool intersect_A(LINESEG u,LINESEG v)return intersect(u,v) & !online(u,v.st) & !online(u,v.ed) & !online(v,u.st) & !online(u,v.ed);bool intersect_L(LINESEG u,L

7、INESEG v)return multiply(u.st,v.ed,v.st)*multiply(v.ed,u.ed,v.st)=0;bool intersection_line(LINE L1,LINE L2,Point &inter)if (fabs(det)EPS) return false;return true;bool intersection_lineseg(LINESEG u,LINESEG v,Point &inter)LINE L1,L2;L1=makeline(u.st,u.ed);L2=makeline(v.st,v.ed);if (intersection_line

8、(L1,L2,inter) return online(u,inter) & online(v,inter);else return false;bool intersection_LLS(LINE L1,LINESEG u,Point &inter)LINE L2;L2=makeline(u.st,u.ed);if (intersection_line(L1,L2,inter) return online(u,inter);else return false;int Inside(Point q,int n)Point q2;const int on_edge=0;int i=0,count

9、;pn=p0;while (in)for (count=0,i=0,q2.x=rand()+offset,q2.y=rand()+offset;in;i+)if (zero(multiply(q,pi,pi+1) & (pi.x-q.x)*(pi+1.x-q.x)EPS & (pi.y-q.y)*(pi+1.y-q.y)EPS)return on_edge;else if (zero(multiply(q,q2,pi)break;else if (multiply(q,pi,q2)*multiply(q,pi+1,q2)-EPS & multiply(pi,q,pi+1)*multiply(p

10、i,q2,pi+1)-EPS)count+;return count&1; bool cmp(Point p,Point q)if (p.xq.x) return false;if (p.yq.y) return true;return false;/线段与多边形相交定义为至少有1个点在多边形内，返回true; bool LINESEG_intersect_Polygon(LINESEG LS1,int n) LINESEG LS2;Point mid;int i;int j,top;Point stackM;pn=p000;for(i=0;in;i+)LS2.st=pi;LS2.ed=pi+

11、1;if (intersect_A(LS1,LS2) return true;top=0;stacktop+=LS1.st;stacktop+=LS1.ed;for(i=0;in;i+)if (online(LS1,pi) stacktop+=pi;sort(stack,stack+top,cmp);stacktop=stack0;for(j=0;jtop;j+)mid.x=(stackj.x+stackj+1.x)/2;mid.y=(stackj.y+stackj+1.y)/2;if (Inside(mid,n) return true;return false;const int M=15

12、000;struct Linedouble a,b,c;LM;struct Pointdouble x,y; pM,ppM;/由两点化一般式Line LineChange(Point P1,Point P2) Line K;K.a=P2.y-P1.y;/(y2-y1)*x+(x1-x2)*y-(x1-x2)*y1-x1*(y2-y1)=0;counterclockK.b=P1.x-P2.x; return k;/求两直线交点bool GetSegcross(Line K1,Line K2,Point &pp)if (fabs(det)1e-8) return 0;return 1;/p在直线上

13、返回0.00double p_on_line(Line K,Point p) /求两点的垂直平分线void MidLine(Point P1,Point P2,Line &K)K.a=2*(P1.x-P2.x);K.b=2*(P1.y-P2.y);K.c=(-K.a*(P1.x+P2.x)-K.b*(P1.y+P2.y)/2;/求任意点对的最小距离，分治nlogn.double nearest(Point *p, int n) /p should already be sorted by xif(n=2) return dist(p0, p1);if(n=1) return INF;int m=pn/2.x,i,j; double left,right,tmp,ret,t;left=nearest(p,n/2);right=nearest(&pn/2,n-n/2);ret=