5.1.1 Fencing the Cows 圈奶牛
时间： 1ms 内存：64M
描述：
农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。
输入：
输入数据的第一行包括一个整数 N。N（0 <= N <= 10,000）表示农夫约翰想要围住的放牧点的数目。接下来 N 行，每行由两个实数组成，Xi 和 Yi,对应平面上的放牧点坐标（-1,000,000 <= Xi,Yi <= 1,000,000）。数字用小数表示。
输出：
输出必须包括一个实数，表示必须的围栏的长度。答案保留两位小数。
示例输入：
4
4 8
4 12
5 9.3
7 8
示例输出：
12.00
提示：
参考答案（内存最优[1520]）：
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
struct point
{
double x, y;
};
bool mult(point sp,point ep,point op){
return (sp.x-op.x)*(ep.y-op.y)>=(ep.x-op.x)*(sp.y-op.y);
}
bool operator < (const point &l,const point &r)
{
return l.y<r.y||(l.y==r.y&&l.x<r.x);
}
int gra(point pnt[],int n,point res[])
{
int i,len,top=1;
sort(pnt,pnt+n);
if(n==0)return 0;res[0]=pnt[0];
if(n==1)return 1;res[1]=pnt[1];
if(n==2)return 2;res[2]=pnt[2];
for(i=2;i<n;i++){
while(top&&mult(pnt[i],res[top],res[top-1]))
top--;
res[++top]=pnt[i];
}
len=top;
res[++top]=pnt[n-2];
for(i=n-3;i>=0;i--){
while(top!=len&&mult(pnt[i],res[top],res[top-1]))
top--;
res[++top]=pnt[i];
}
return top;
}
double dis(point a,point b)
{
return sqrt(pow(fabs(a.x-b.x),2)+pow(fabs(a.y-b.y),2));
}
int main()
{
int n,i;
double a,b,sumx;
point p[10001],r[10001];
while(cin>>n){
for(i=0;i<n;i++){
cin>>a>>b;
p[i].x=a;
p[i].y=b;
}
int x=gra(p,n,r);
sumx=0;
for(i=1;i<x;i++){
sumx+=dis(r[i],r[i-1]);
}
sumx+=dis(r[0],r[x-1]);
printf("%.2lf\n",sumx);
}
return 0;
}参考答案（时间最优[108]）：
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
struct point
{
double x, y;
};
bool mult(point sp,point ep,point op){
return (sp.x-op.x)*(ep.y-op.y)>=(ep.x-op.x)*(sp.y-op.y);
}
bool operator < (const point &l,const point &r)
{
return l.y<r.y||(l.y==r.y&&l.x<r.x);
}
int gra(point pnt[],int n,point res[])
{
int i,len,top=1;
sort(pnt,pnt+n);
if(n==0)return 0;res[0]=pnt[0];
if(n==1)return 1;res[1]=pnt[1];
if(n==2)return 2;res[2]=pnt[2];
for(i=2;i<n;i++){
while(top&&mult(pnt[i],res[top],res[top-1]))
top--;
res[++top]=pnt[i];
}
len=top;
res[++top]=pnt[n-2];
for(i=n-3;i>=0;i--){
while(top!=len&&mult(pnt[i],res[top],res[top-1]))
top--;
res[++top]=pnt[i];
}
return top;
}
double dis(point a,point b)
{
return sqrt(pow(fabs(a.x-b.x),2)+pow(fabs(a.y-b.y),2));
}
int main()
{
int n,i;
double a,b,sumx;
point p[10001],r[10001];
while(cin>>n){
for(i=0;i<n;i++){
cin>>a>>b;
p[i].x=a;
p[i].y=b;
}
int x=gra(p,n,r);
sumx=0;
for(i=1;i<x;i++){
sumx+=dis(r[i],r[i-1]);
}
sumx+=dis(r[0],r[x-1]);
printf("%.2lf\n",sumx);
}
return 0;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。