Graham求凸包模板

时间:2021-02-02 03:22:45
 struct P
{
double x, y;
P(double x=, double y=):x(x), y(y) {}
double add(double a, double b){
if(fabs(a+b)<eps*(fabs(a)+fabs(b))) return ;
return a+b;
}
P operator + (P p){
return P(add(x, p.x), add(y, p.y));
}
P operator - (P p){
return P(add(x, -p.x), add(y, -p.y));
}
P operator *(double d){
return P(x*d, y*d);
}
double dot(P p){ //点积
return add(x*p.x, y*p.y);
}
double det(P p){ //差积
return add(x*p.y, -y*p.x);
}
}ps[N]; double dist(P a, P b){
return sqrt((b-a).dot(b-a));
} bool cmp_x(const P& p, const P& q){
if(p.x!=q.x) return p.x < q.x;
return p.y < q.y;
}
//返回求得的凸包
vector<P> convex_hull(P *ps, int n){
sort(ps,ps+n,cmp_x);
int k = ; //凸包顶点数
vector<P> qs(n*);
//构造凸包的下侧
for(int i=; i<n; i++)
{
while(k> && (qs[k-]-qs[k-]).det(ps[i]-qs[k-])<=) k--;
qs[k++] = ps[i];
}
//构造凸包的上侧
for(int i=n-,t=k; i>=; i--)
{
while(k>t && (qs[k-]-qs[k-]).det(ps[i]-qs[k-])<=) k--;
qs[k++] = ps[i];
}
qs.resize(k-);
return qs;
}