【-90】P2742 [USACO5.1]圈奶牛Fencing the Cows[凸包]

题目描述

农夫约翰想要建造一个围栏用来围住他的奶牛,可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标,计算最短的能够围住这些点的围栏的长度。

输入输出格式

输入格式:

输入数据的第一行包括一个整数 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

题解

裸题
暴搞的凸包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
int n;
int i;
struct node
{
double x;
double y;
}a[10100];
int stack[10100],top;
double sum;
bool cmp(node aa,node bb)
{
return aa.x<bb.x;
}
bool pd(int u,int v,int w)
{
return (a[u].y-a[v].y)*(a[v].x-a[w].x)>(a[v].y-a[w].y)*(a[u].x-a[v].x);
}
int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%lf%lf",&a[i].x,&a[i].y);
}
sort(a+1,a+n+1,cmp);
//下面部分
stack[1]=1;
stack[2]=2;
top=2;
for (i=3;i<=n;i++)
{
while (top>1&&pd(stack[top-1],stack[top],i)) top--;
stack[++top]=i;
}
for (i=2;i<=top;i++)
{
sum+=sqrt(((a[stack[i-1]].x-a[stack[i]].x)*(a[stack[i-1]].x-a[stack[i]].x))+((a[stack[i-1]].y-a[stack[i]].y)*(a[stack[i-1]].y-a[stack[i]].y)));
}
//上面部分
stack[1]=1;
stack[2]=2;
top=2;
for (i=3;i<=n;i++)
{
while (top>1&&!pd(stack[top-1],stack[top],i)) top--;
stack[++top]=i;
}
for (i=2;i<=top;i++)
{
sum+=sqrt(((a[stack[i-1]].x-a[stack[i]].x)*(a[stack[i-1]].x-a[stack[i]].x))+((a[stack[i-1]].y-a[stack[i]].y)*(a[stack[i-1]].y-a[stack[i]].y)));
}
printf("%.2lf",sum);
return 0;
}