[文章目录]
Description
农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。n<=1000
凸包就是平面上给你一堆点，最外圈的那些点
如何求凸包？首先找到一个一定在外圈上的点（横坐标最小的点），设为O点。然后将其他点按照关于这个点的极角排序（通过向量叉积判断极角的相对大小），扔入栈中。扫一圈，每次通过栈顶两边的点判断弹出栈顶的点，条件： 栈顶与栈中点形成的向量 与 加入点与栈中点形成的向量 叉乘为正。
叉乘定义：
由叉乘的分配律得：
(x1,y1) x (x2,y2)=x1y2-x2y1
如果值大于零，说明这个向量转到下一个向量的转角的sin大于零，说明这个点就在由(O,栈顶下面的点，要加入的点)构成的三角形里，因此可以排除这个点。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
double ans;
struct node
{
double x,y;
}a[10100];
bool cmp(node x,node y) {return x.x==y.x ? x.y<y.y:x.x<y.x;}
double cross(int x,int y,int o)
{
return (a[x].x-a[o].x)*(a[y].y-a[o].y)-(a[y].x-a[o].x)*(a[x].y-a[o].y);
}
bool cmp1(node x,node y)
{
return (x.y-a[1].y)*(y.x-a[1].x)<(y.y-a[1].y)*(x.x-a[1].x);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
sort(a+2,a+n+1,cmp1);
int top=3;
for(int i=4;i<=n;i++)
{
while(top>=3&&cross(top-1,i,top)>0) top--;
a[++top]=a[i];
}
for(int i=1;i<top;i++)
ans+=sqrt((a[i+1].x-a[i].x)*(a[i+1].x-a[i].x)+(a[i+1].y-a[i].y)*(a[i+1].y-a[i].y));
ans+=sqrt((a[top].x-a[1].x)*(a[top].x-a[1].x)+(a[top].y-a[1].y)*(a[top].y-a[1].y));
printf("%.2lf",ans);
return 0;
}