本文共 3714 字，大约阅读时间需要 12 分钟。

typedef double db ;const int maxn = 1e5 + 10 ;const db eps = 1e-6 ;const db pi = acos(-1.0) ;int sgn(db x){    if(x < -eps) return -1 ;  else if (x > eps)  return 1 ;  else return 0 ;}void prin(int num , db x){    cout << fixed << setprecision(num) << x << '\n' ;}struct point{    db x , y ;    point(){}    point(db _x , db _y)    {        x = _x , y = _y ;    }    void scan()    {        db k1 , k2 ;        cin >> k1 >> k2 ;        x = k1 , y = k2 ;    }    void print()    {        cout << fixed << setprecision(12) << x << ' ' << y << '\n' ;    }    point operator + (const point& s) const    {        return point(x + s.x , y + s.y) ;    }    point operator - (const point& s) const    {        return point(x - s.x , y - s.y) ;    }    point operator * (const db& k) const    {        return point(x * k , y * k) ;    }    point operator / (const db& k) const    {        return point(x / k , y / k) ;    }    db get_angle()//极角    {        return atan2(y , x) ;    }     bool operator == (point b) const    {        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0 ;    }    bool operator < (point b)const    {        return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x ;    }    db sqr(db x)    {        return x * x ;    }    db len() //与原点的距离    {        return sqrt(sqr(x) + sqr(y)) ;    }    db dis(point p) //返回两点间的距离    {        return sqrt(sqr(x - p.x) + sqr(y - p.y)) ;    }    // db rad(point a , point b) //向量p->a和p->b的夹角 ?    // {            // }    // point trunc(db r) //化为长度为r的向量 ?    // {    //     db l = len() ;    //     if(!sgn(l))  return *this ;    //     r /= l ;    //     return point(x * r , y * r) ;    // }    // point rot_left() //逆时针旋转90度 ?    // {    //     return point(-y , x) ;    // }    // point rot_right() //顺时针旋转90度 ?    // {    //     return point(y , -x) ;    // }    // point rotate(point p , db angle) //绕a点逆时针旋转angle ?    // {    //     point v = (*this) - p ;    //     db c = cos(angle) , s = sin(angle) ;    //     return point(p.x + v.x * c - v.y * s , p.y + v.x * s + v.y * c) ;     // }} ;db cross(point k1 , point k2) //叉积{    return k1.x * k2.y - k1.y * k2.x ;}db dot(point k1 , point k2) //点积{    return k1.x * k2.x + k1.y * k2.y ;}struct line{    point s , e ;    line(){}    line(point _s , point _e)    {        s = _s , e = _e ;    }    db len()    {        return s.dis(e) ;    }    void adjust()    {        if(e < s)  swap(s , e) ;    }    // db dis_point_to_line(point p) //点a到直线的距离 ?    // {            // }    // db dis_point_to_seg(point p) //点a到线段的距离 ?    // {            // }    // pair
   
     operator &(const line &b) const //直线相交求交点 ?    // {            // }    // int relation(point p) //点和有向直线关系 ?    // {            // }    // bool point_on_seg(point p)  // ?     // {            // }} ;//凸包面积db area(vector
    
      A) // 多边形用 vector
     
       表示 , 逆时针 {    db ans = 0 ;    for(int i = 0 ; i < (int)A.size() ; i ++)  ans += cross(A[i] , A[(i + 1) % (int)A.size()]) ;    return fabs(ans) / 2 ;}//凸包周长db perimeter(vector
      
        A) // 多边形用 vector
       
         表示 , 逆时针 {    db ans = 0 ;    for(int i = 0 ; i < (int)A.size() ; i ++)  ans += A[i].dis(A[(i + 1) % (int)A.size()]) ;    return ans ;}//凸包vector
        
          ConvexHull(vector
         
           A , int flag = 1) // flag = 0 不严格 flag = 1 严格 { int n = A.size() ; vector
          
            ans(n * 2) ; sort(A.begin() , A.end()) ; int now = -1 ; for(int i = 0 ; i < (int)A.size() ; i ++) { while(now > 0 && sgn(cross(ans[now] - ans[now - 1] , A[i] - ans[now - 1])) < flag) now -- ; ans[++ now] = A[i] ; } int pre = now ; for(int i = n - 2 ; i >= 0 ; i --) { while(now > pre && sgn(cross(ans[now] - ans[now - 1] , A[i] - ans[now - 1])) < flag) now -- ; ans[++ now] = A[i] ; } ans.resize(now) ; return ans ;}