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

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

#include

#include

#include

#include

using nameaace std;

const int M=100000+5;

struct Point

{

double x,y;

} p[M];

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

if (a.x>b.x) return false;

if (a.y

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在左手边，逆时针

}

bool bo[M];

Point pp[M];

int stack[M]; //from 1 to t

void 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;i<=n;i++){ //合并排序

if (i>1 && p[i].x==p[i-1].x && p[i].y==p[i-1].y) continue;

p[++t]=p[i];

}

n=t; t=0;

memset(bo+1,true,n*sizeof(bo[0]));

if (n>0){

stack[++t]=1;

bo[stack[t]]=false;

}

if (n>1){

stack[++t]=2;

bo[stack[t]]=false;

}

if (n>2){

for(i=3;i

if(bo[i] && Xdet(p[stack[t-1]],p[stack[t]],p[i])>=0) stack[++t]=i,bo[i]=false;

else{

while(t>=2&& Xdet(p[stack[t-1]],p[stack[t]],p[i])<0) bo[stack[t]]=true,t--;

stack[++t]=i;

bo[stack[t]]=false;

}

for(i=n;i>=1;i--)

if (bo[i] && Xdet(p[stack[t-1]],p[stack[t]],p[i])>=0) stack[++t]=i,bo[i]=false;

else{

while(t>=2&&Xdet(p[stack[t-1]],p[stack[t]],p[i])<0) bo[stack[t]]=true,t--;

stack[++t]=i;

bo[stack[t]]=false;

}

t--;

}

for(i=1;i<=t;i++) pp[i]=p[stack[i]];

memcpy(p+1,pp+1,t*sizeof(Point));

n=t;

}

求凸点集的面积

double area(Point *p,int n)

{

double sum=0;

int i;

p[n+1]=p[1];

for(i=1;i<=n;i++)

sum+=p[i].x*p[i+1].y-p[i].y*p[i+1].x;

return sum/2.0;

}

const double EPS=1e-9;

const double maxn=1e6-1;

const double PI=acos(-1.);

const int M=100+5;

const double offset=11213;

#define zero(x) (((x)>0?(x):-(x))

struct Point{

double x,y;

} p[M];

struct LINESEG{

Point st,ed;

};

struct LINE{

double 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,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){

return fabs(multiply(L.ed,q,L.st))

LINE makeline(Point p1,Point p2){

LINE tl;

tl.a=p2.y-p1.y; tl.b=p1.x-p2.x;

tl.c=p1.y*p2.x-p1.x*p2.y;

if (tl.a

return tl;

}

inline double MAX(double x,double y){return x>y?x:y;}

inline double MIN(double x,double y){return x

bool intersect(LINESEG u,LINESEG v){

return MAX(u.st.x,u.ed.x)>=MIN(v.st.x,v.ed.x)

&& MAX(v.st.x,v.ed.x)>=MIN(u.st.x,u.ed.x)

&& MAX(u.st.y,u.ed.y)>=MIN(v.st.y,v.ed.y)

&& MAX(v.st.y,v.ed.y)>=MIN(u.st.y,u.ed.y)

&& 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(LINESEG u,LINESEG v){