凸包专题总结

1.安德鲁算法求 上+下凸包

2.Q.resize(k)和Q.reszie(k+1)的问题

3.几何题精度double和long long 避免混用，判断正负用sign

4.求凸包面积（无精度差），凸包周长

5.稳定凸包的理解：即不存在一个点，使得原先凸包上的点不再是新凸包上的点。即凸包上每条边，都有>=3个点存在

6.极角排序/ 求凸包后也是极角排序

这些总结都是从已发过的文章里总结出来。可以看博客分栏的凸包专题

模板：

求凸包面积
#include<cstdio>
#include<vector>
#include<cmath>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=3e5+5;
const int MOD=1e9+7;
template <class T>
bool sf(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='\n'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}
int sign(double x){
    return abs(x)<1e-7?0:x<0?-1:1;
}
struct Point{
    double x,y;
    Point(double x=0.0, double y=0.0) : x(x), y(y) {}
    Point operator - (const Point &rhs) const{
        return Point(x-rhs.x,y-rhs.y);
    }
    bool operator == (const Point &rhs) const{
        return sign(x-rhs.x)==0&&sign(y-rhs.y)==0;
    }
    bool operator < (const Point &rhs)const{
        if(x==rhs.x)    return y<rhs.y;
        else    return x<rhs.x;
    }
};
typedef Point Vector;
double cross(Vector A,Vector B){
    return (double)A.x*B.y-(double)A.y*B.x;
}
int n;
typedef vector<Point> Polygon;
Polygon convex_hull(Polygon P) {
    sort(P.begin(), P.end());  //排序
    P.erase(unique(P.begin(), P.end()), P.end());  //删除重复点
    int n = P.size(), k = 0;
    Polygon Q(n*2);
    for (int i=0; i<n; ++i) {//求解下凸包
        while (k > 1 && cross(Q[k-1]-Q[k-2], P[i]-Q[k-2]) <= 0) k--;
        Q[k++] = P[i];
    }
    for (int t=k, i=n-2; i>=0; --i) {
        while (k > t && cross(Q[k-1]-Q[k-2], P[i]-Q[k-2]) <= 0) k--;
        Q[k++] = P[i];
    }
    Q.resize(k);// resize k 把第一个进入的点再算了一次，实际数量比凸包的个数要多1个点。具体需要具体使用，求周长和求面积方便求。
    return Q;
}
int main(void){
    while(cin>>n){
        Polygon t;
        for(int i=1;i<=n;i++){
            double x,y;
            scanf("%lf%lf",&x,&y);
            t.push_back({x,y});
        }
        vector<Point> ans=convex_hull(t);
        double res=0.0;
        for(int i=0;i<(int)ans.size()-1;++i)    res+=cross(ans[i],ans[i+1]);
        if(res<0)   res=-res;
        res/=2.;
    }
    return 0;
}