本文主要是介绍NYOJ 78 - 圈水池，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
描述
有一个牧场，牧场上有很多个供水装置，现在牧场的主人想要用篱笆把这些供水装置圈起来，以防止不是自己的牲畜来喝水，各个水池都标有各自的坐标，现在要你写一个程序利用最短的篱笆将这些供水装置圈起来！（篱笆足够多，并且长度可变）
输入
第一行输入的是N,代表用N组测试数据（1<=N<=10）
第二行输入的是m,代表本组测试数据共有m个供水装置（3<=m<=100）
接下来m行代表的是各个供水装置的横纵坐标
输出
输出各个篱笆经过各个供水装置的坐标点，并且按照x轴坐标值从小到大输出，如果x轴坐标值相同，再安照y轴坐标值从小到大输出
样例输入
1
4
0 0
1 1
2 3
3 0
样例输出
0 0
2 3
3 0
因为一直没有学凸包，就拿了个入门题来练练手，熟悉一下什么叫凸包。
只要挨着判断已经入栈的元素是否符合要求就行了，至于凸包大家应该都会。
#include <cstdio>
#include <algorithm>
using namespace std;struct node
{int x, y;
};
node points[105], s[105];int cmp(node a, node b)
{if (a.x == b.x)return a.y < b.y;return a.x < b.x;
}bool mul(node a, node b, node c)//计算叉积函数
{int abx, aby, acx, acy;abx = b.x - a.x;aby = b.y - a.y;acx = c.x - a.x;acy = c.y - a.y;if (abx*acy - aby*acx > 0)//如果是逆时针return true;return false;
}int main()
{int T, n;int top;scanf("%d", &T);while (T--){scanf("%d", &n);for (int i = 0; i < n; ++i)scanf("%d%d", &points[i].x, &points[i].y);sort(points, points+n, cmp);//先排序出选择的顺序top = 0;for (int i = 0; i < n; ++i)//下凸包{while (top >= 2 && !mul(s[top-2], s[top-1], points[i]))top--;s[top++] = points[i];}int cur = top - 1;for (int i = n-1; i >= 0; --i)//上凸包{while (top >= cur+2 && !mul(s[top-2], s[top-1], points[i]))top--;s[top++] = points[i];}--top;//下凸包的结尾和上凸包的开始一样，所以删去这个sort(s, s+top, cmp);for (int i = 0; i < top; ++i)printf("%d %d\n", s[i].x, s[i].y);}return 0;
}
这篇关于NYOJ 78 - 圈水池的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
