nyoj 78-圈水池 (凸包)

78-圈水池

内存限制:64MB 时间限制:3000ms 特判: No
通过数:5 提交数:6 难度:4

题目描述:

有一个牧场，牧场上有很多个供水装置，现在牧场的主人想要用篱笆把这些供水装置圈起来，以防止不是自己的牲畜来喝水，各个水池都标有各自的坐标，现在要你写一个程序利用最短的篱笆将这些供水装置圈起来！（篱笆足够多，并且长度可变）

输入描述:

第一行输入的是N,代表用N组测试数据（1<=N<=10）
第二行输入的是m,代表本组测试数据共有m个供水装置（3<=m<=100）
接下来m行代表的是各个供水装置的横纵坐标

输出描述:

输出各个篱笆经过各个供水装置的坐标点，并且按照x轴坐标值从小到大输出，如果x轴坐标值相同，再安照y轴坐标值从小到大输出

样例输入:

样例输出:

0 0
2 3
3 0

分析：
　　1、凸包裸题
　　2、说明，凸包问题可以用来求一个块区域的最值问题
　　3、上凸包 + 下凸包 ==> 最短的篱笆

核心代码：

 1 int cnt = 0;
 2 for(int i = 0; i < n; ++ i) // 下凸包
 3 {
 4     while(cnt > 1 && cross_product(ans[cnt-2], ans[cnt-1], P[i]) <= 0)
 5         -- cnt;
 6     ans[cnt ++] = P[i];
 7 }
 8 int temp = cnt;
 9 for(int i = n-1; i >= 0; -- i)
10 {
11     while(cnt > temp && cross_product(ans[cnt-2], ans[cnt-1], P[i]) <= 0)
12         -- cnt;
13     ans[cnt ++] = P[i];
14 }
15 -- cnt;

C/C++代码实现（AC）：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <stack>
 7 #include <map>
 8 #include <queue>
 9 #include <set>
10 
11 using namespace std;
12 const int MAXN = 105;
13 struct node
14 {
15     int x, y;
16 }P[MAXN], ans[MAXN];
17 
18 bool cmp(node a, node b)
19 {
20     if (a.x != b.x) return a.x < b.x;
21     return a.y < b.y;
22 }
23 
24 int cross_product(node a, node b, node c)
25 {
26     return ((b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x));
27 }
28 
29 int main()
30 {
31     int N;
32     scanf("%d", &N);
33     while(N --)
34     {
35         int n, cnt = 0;
36         scanf("%d", &n);
37         for (int i = 0; i < n; ++ i)
38             scanf("%d%d", &P[i].x, &P[i].y);
39 
40         sort (P, P+n, cmp);
41         for(int i = 0; i < n; ++ i) // 下凸包
42         {
43             while(cnt > 1 && cross_product(ans[cnt-2], ans[cnt-1], P[i]) <= 0)
44                 -- cnt;
45             ans[cnt ++] = P[i];
46         }
47         int temp = cnt;
48         for(int i = n-1; i >= 0; -- i) // 上凸包
49         {
50             while(cnt > temp && cross_product(ans[cnt-2], ans[cnt-1],P[i]) <= 0)
51                 -- cnt;
52             ans[cnt ++] = P[i];
53         }
54         -- cnt;
55         sort (ans, ans + cnt, cmp);
56         for (int i = 0; i < cnt; ++ i)
57             printf("%d %d
", ans[i].x, ans[i].y);
58     }
59     return 0;
60 }