把點(diǎn)集凸包化Granham-Scan算法(使用水平序)

1、把點(diǎn)集凸包化Granham-Scan算法（使用水平序）#include<stdio.h>#include<string.h>#include<math.h>#include<algorithm>using 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.x&l

2、t;b.x) return true;if (a.x>b.x) return false;if (a.y<b.y) return true;return false;double Xdet(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在左手邊，逆時(shí)針bool boM;Point ppM;int stackM; /from 1 to tvoid Gram_Scan(Point *p,int &n) /

3、p從1-n,把點(diǎn)集土包化 n*log(n);int i,t;sort(p+1,p+1+n,cmp);for(t=0,i=1;i<=n;i+)/合并排序if (i>1 && pi.x=pi-1.x && pi.y=pi-1.y) continue;p+t=pi;n=t;t=0;memset(bo+1,true,n*sizeof(bo0);if (n>0)stack+t=1;bostackt=false;if (n>1)stack+t=2;bostackt=false;if (n>2)for(i=3;i<n;i+)if(boi &

4、amp;& Xdet(pstackt-1,pstackt,pi)>=0) stack+t=i,boi=false;elsewhile(t>=2&& Xdet(pstackt-1,pstackt,pi)<0) bostackt=true,t-;stack+t=i;bostackt=false;for(i=n;i>=1;i-)if (boi && Xdet(pstackt-1,pstackt,pi)>=0) stack+t=i,boi=false;elsewhile(t>=2&&Xdet(pstackt-1

5、,pstackt,pi)<0) 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;求凸點(diǎn)集的面積double area(Point *p,int n)double sum=0;int i;pn+1=p1;for(i=1;i<=n;i+)sum+=pi.x*pi+1.y-pi.y*pi+1.x;return sum/2.0;const double EPS=1e-9;const double maxn=1e6-1

6、;const double PI=acos(-1.);const int M=100+5;const double offset=11213;#define zero(x) (x)>0?(x):-(x)<EPS)struct Pointdouble x,y; pM;struct LINESEGPoint st,ed;struct LINEdouble a,b,c;double dist(Point a,Point b)return sqrt(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);double multiply(Point a,Point b,

7、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.a=p2.y-p1.y;tl.b=p1.x-p2.x;if (tl.a<EPS) tl.a=-tl.a,tl.b=-tl.b,tl.c=-tl.c;retu

8、rn tl;inline double MAX(double x,double y)return x>y?x:y;inline double MIN(double x,double y)return x<y?x:y;bool intersect(LINESEG u,LINESEG v)&& multiply(v.st,u.ed,u.st)*multiply(u.ed,v.ed,u.st)>=0&& multiply(u.st,v.ed,v.st)*multiply(v.ed,u.ed,v.st)>=0;bool intersect_A(L

9、INESEG 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,LINESEG 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 &i

10、nter)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(L1,L2,inter) return online(u,inter) && online(v,inter);else return false;bool intersection_LLS(LIN

11、E 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;pn=p0;while (i<n)for (count=0,i=0,q2.x=rand()+offset,q2.y=rand()+offset;i<n;i+)if (zero

12、(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(pi,q2,pi+1)<-EPS)count+;return count&1; b

13、ool cmp(Point p,Point q)if (p.x<q.x) return true;if (p.x>q.x) return false;if (p.y<q.y) return true;return false;/線段與多邊形相交定義為至少有1個(gè)點(diǎn)在多邊形內(nèi)，返回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;i<n;i+)LS2.st=pi;LS2.ed=pi

14、+1;if (intersect_A(LS1,LS2) return true;top=0;stacktop+=LS1.st;stacktop+=LS1.ed;for(i=0;i<n;i+)if (online(LS1,pi) stacktop+=pi;sort(stack,stack+top,cmp);stacktop=stack0;for(j=0;j<top;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

15、 int M=15000;struct Linedouble a,b,c;LM;struct Pointdouble x,y; pM,ppM;/由兩點(diǎn)化一般式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;/求兩直線交點(diǎn)bool GetSegcross(Line K1,Line K2,Point &pp)if (fabs(det)<1e-8) return

16、0;return 1;/p在直線上返回0.00double p_on_line(Line K,Point p) /求兩點(diǎn)的垂直平分線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;/求任意點(diǎn)對(duì)的最小距離，分治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=tmp =left<right?left