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;
}