题目描述
农夫约翰想要建造一个围栏用来围住他的奶牛,可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标,计算最短的能够围住这些点的围栏的长度。
输入输出格式
输入格式:
输入数据的第一行包括一个整数 N。N(0 <= N <= 10,000)表示农夫约翰想要围住的放牧点的数目。接下来 N 行,每行由两个实数组成,Xi 和 Yi,对应平面上的放牧点坐标(-1,000,000 <= Xi,Yi <= 1,000,000)。数字用小数表示。
输出格式:
输出必须包括一个实数,表示必须的围栏的长度。答案保留两位小数。
输入输出样例
输入样例#1:
4
4 8
4 12
5 9.3
7 8
输出样例#1:
12.00
说明
题目翻译来自NOCOW。
USACO Training Section 5.1
解题思路
一道裸的凸包周长。
凸包周长~直径多长~一进考场~全都忘光——
我是从
这里学到的姿势,直接上模板吧。
还有,极角排序不能用斜率!要用叉积!
源代码
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
struct node{
double x;
double y;
double k;
bool operator < (const node & a) const{//极角排序
if(fabs(k-a.k)<1e-5)
{
return (x*x+y*y)<(a.x*a.x+a.y*a.y);
}
return (k<a.k);
}
}p[100010];
double X(node a,node b,node c)//叉积
{
double x1=b.x-a.x,y1=b.y-a.y;
double x2=c.x-a.x,y2=c.y-a.y;
return x1*y2-x2*y1;
}
double len(node a,node b){return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );}//勾股
node s[100010]={0};
int top=0;
int main()
{
scanf("%d",&n);
if(n==1||n==0){printf("0");return 0;}
for(int i=1;i<=n;i++)//输入
{
double x,y;
scanf("%lf%lf",&x,&y);
p[i]={x,y};
if(p[i].y<p[1].y) swap(p[1],p[i]);
else if(fabs(p[i].y-p[1].y)<1e-6&&p[i].x<p[1].x) swap(p[1],p[i]);
}
if(n==2){printf("%lf",len(p[1],p[2]));return 0;}
for(int i=2;i<=n;i++)//挪原点
{
p[i].x-=p[1].x;
p[i].y-=p[1].y;
p[i].k=p[i].y/p[i].x;
}
p[1]={0.0,0.0};
sort(p+2,p+1+n);
s[top++]=p[1];
s[top++]=p[2];
p[++n]=p[1];
for(int i=3;i<=n;i++)//求凸包
{
while(top!=0&&X(s[top-2],s[top-1],p[i])<0)top--;
s[top++]=p[i];
}
double ans=0;
//for(int i=1;i<=n;i++) printf("^%lf^%lf^\n",p[i].x,p[i].y);
do//求周长
{
ans+=len(s[top-1],s[top-2]);
top--;
}while(top);
printf("%.2lf\n",ans);
return 0;
}