题解 | 护城河-牛客假日团队赛5J题
J-护城河_牛客假日团队赛5
https://ac.nowcoder.com/acm/contest/984/J
题目描述
为了防止口渴的食蚁兽进入他的农场，Farmer John决定在他的农场周围挖一条护城河。农场里一共有N(8<=N<=5,000)股泉水，并且，护城河总是笔直地连接在河道上的相邻的两股泉水。护城河必须能保护所有的泉水，也就是说，能包围所有的泉水。泉水一定在护城河的内部，或者恰好在河道上。当然，护城河构成一个封闭的环。
挖护城河是一项昂贵的工程，于是，节约的FJ希望护城河的总长度尽量小。请你写个程序计算一下，在满足需求的条件下，护城河的总长最小是多少。
所有泉水的坐标都在范围为(1..10,000,000,1..10,000,000)的整点上，一股泉水对应着一个唯一确定的坐标。并且，任意三股泉水都不在一条直线上。
以下是一幅包含20股泉水的地图，泉水用"*"表示：
挖护城河是一项昂贵的工程，于是，节约的FJ希望护城河的总长度尽量小。请你写个程序计算一下，在满足需求的条件下，护城河的总长最小是多少。
所有泉水的坐标都在范围为(1..10,000,000,1..10,000,000)的整点上，一股泉水对应着一个唯一确定的坐标。并且，任意三股泉水都不在一条直线上。
以下是一幅包含20股泉水的地图，泉水用"*"表示：
图中的直线，为护城河的最优挖掘方案，即能围住所有泉水的最短路线。...*-----------------*......
../..........*........\.....
./.....................\....
*......................*\...
|..........*........*....\..
|*........................\.
|..........................*
*..........................|
.\*........................|
..\.....................*..|
...\........*............*.|
....\..................*...*
.....\..*..........*....../.
......\................../..
.......*----------------*...
（请复制到记事本中用等宽字体查看）
路线从左上角起，经过泉水的坐标依次是：(18,0),(6,-6),(0,-5),(-3,-3),(-17,0),(-7,7),(0,4),(3,3)。绕行一周的路径总长为70.8700576850888(...)。答案只需要保留两位小数，于是输出是70.87。
输入描述:
第1行: 一个整数，N
第2..N+1行: 每行包含2个用空格隔开的整数，x[i]和y[i]，即第i股泉水的位置坐标
输出描述:
第1行: 输出一个数字，表示满足条件的护城河的最短长度。保留两位小数
示例1
输入
20
2 10
3 7
22 15
12 11
20 3
28 9
1 12
9 3
14 14
25 6
8 1
25 1
28 4
24 12
4 15
13 5
26 5
21 11
24 4
1 8
输出
70.87
解答
题目大意 ： 有N个泉水，只能在各个泉水之间连线，输出最少的路程可以将所有泉水围住
思路 ：先对坐标进行排序，找到最下面的点，如果有多个选取任意一个都行，然后把第一个点存到栈中，对其他点按照极角大小进行排序 （极角相同则距离第一个点近的靠前），将排序后的第一个点存入栈，再依次遍历其他点，如果栈顶的两个元素A, B,与该点C满足 ：向量AC 在向量BC的左边，那么就将C加入栈，否则，弹出栈顶元素，再用栈顶前两个元素与该点进行判断，最后输入每个点之间的距离即可
AC代码 ：
来源：东野圭吾#
思路 ：先对坐标进行排序，找到最下面的点，如果有多个选取任意一个都行，然后把第一个点存到栈中，对其他点按照极角大小进行排序 （极角相同则距离第一个点近的靠前），将排序后的第一个点存入栈，再依次遍历其他点，如果栈顶的两个元素A, B,与该点C满足 ：向量AC 在向量BC的左边，那么就将C加入栈，否则，弹出栈顶元素，再用栈顶前两个元素与该点进行判断，最后输入每个点之间的距离即可
AC代码 ：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 5;
struct node
{
int x, y;
}p[MAXN], st[MAXN];
int n, xx, yy;
bool cmp1(node a, node b) { // 第一次排序，找到最下面的初始点
if (a.y == b.y) return a.x < b.x;
else return a.y < b.y;
}
int cross(node a, node b, node c) { // 叉积
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
double dis(node a, node b) { // 每个点之间距离
return sqrt((a.x - b.x) * (a.x - b.x) * 1.0 + (a.y - b.y) * (a.y - b.y));
}
bool cmp(node a, node b) { // 第二次对极角进行排序，极角相同按距离从小到大排
int m = cross(p[0], a, b);
if (m > 0) return 1;
else if (!m && dis(p[0], a) - dis(p[0], b) <= 0) return 1;
else return 0;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
if (n == 1) printf("%.2f\n", 0.00);
else if (n == 2) printf("%.2f\n", dis(p[0], p[1]));
else {
sort(p, p + n, cmp1);
st[0] = p[0]; // 保存起始点
xx = st[0].x, yy = st[0].y;
sort(p + 1, p + n, cmp);
st[1] = p[1]; // 保存第二个点
int top = 1;
for (int i = 2; i < n; i++) {
while (i >= 1 && cross(st[top - 1], st[top], p[i]) < 0)
top--;
st[++top] = p[i];
}
double s = 0;
for (int i = 1; i <= top; i++)
s += dis(st[i - 1], st[i]);
s += dis(st[top], p[0]);
printf("%.2f\n", s);
}
return 0;
} 来源：东野圭吾#
