luoguP2742 【模板】二维凸包 / [USACO5.1]圈奶牛 二维凸包

我们知道，纵坐标最小的点一定在凸包上（如果有多个，那它们都会被取到）

随便找一个纵坐标最小的点，将其他所有点按照这个点为原点极角排序，我们发现极角大的会在极角小的后面加入（感性认知一下）

考虑新（加入的点与上一个点的连线）与（上一个点与上上次加入的点的连线）:

如果新的线在上一个线的左边，则没有问题.

如果新的线在上一个线的右边，则新加入的线一定时更优的，上一个线需要被删掉.

一直循环这个过程即可.

既好写，又好调

Code:

#include <cstdio>
#include <algorithm>
#include <cmath> 
#include <cstring>
#define maxn 1000000 
#define inf 1000000000000
#define eps 0.0000000000001
#define p point 
#define setIO(s) freopen(s".in","r",stdin)
using namespace std; 
double tmp=inf,ans; 
int ck; 
struct Point{
    double x,y; 
}point[maxn],s[maxn]; 
double det(double x1,double y1,double x2,double y2){ return x1*y2-x2*y1;  }
double cross(Point a,Point b,Point c){ return det(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);  }
double dis(Point a,Point b){
    double xx=(a.x-b.x)*1.0, yy=(a.y-b.y)*1.0; 
    xx*=xx,yy*=yy; 
    return (double)sqrt(xx+yy); 
}
int exis(double t)
{
    if(fabs(t) < eps) return 0; 
    else return t > eps ? 1 : -1; 
}
bool cmp(Point a,Point b){
    int t=exis(cross(p[1],a,b)); 
    if(t>0) return 1;
    else if(t<0) return 0; 
    else return dis(p[1],a)<dis(p[1],b); 
}
int main(){
    //setIO("input"); 
    int n; 
    scanf("%d",&n); 
    for(int i=1;i<=n;++i) {
        scanf("%lf%lf",&p[i].x,&p[i].y); 
        if(p[i].y<tmp){
            tmp=p[i].y; 
            swap(p[i],p[1]);   
        }
    }
    sort(point+2,point+1+n,cmp);  
    s[1]=p[1]; 
    int tot=1;
    for(int i=2;i<=n;++i) {
        while(tot>1 && cross(s[tot-1],p[i],s[tot]) >= 0) --tot; 
        ++tot;
        s[tot]=p[i]; 
    }
    s[tot+1]=p[1];
    for(int i=1;i<=tot;++i) ans+=dis(s[i],s[i+1]);  
    printf("%.2f
",ans);
    return 0;
}