Algorithm Design—

Algorithm Design——凸包

  1  /**
  2 定义
  3 ⒈ 对于一个集合D，D中任意有限个点的线性组合的全体称为D的凸包。
  4 ⒉ 对于一个集合D，所有包含D的凸集之交称为D的凸包。
  5 可以证明，上述两种定义是等价的
  6 
  7 概念
  8 1. 点集Q的凸包（convex hull）是指一个最小凸多边形，满足Q中的点
  9 或者在多边形边上或者在其内。
 10 2. 一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包
 11 问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用
 12 一根绳子把他们尽量紧地圈起来，并且为凸边形，这就是凸包了。
 13 
 14 常用方法：
 15 穷举法，格雷厄姆扫描法，分治法，蛮力法和Jarris步进法
 16 
 17 格雷厄姆扫描法思路：
 18 （1）求平面点集 S 中 Y 坐标最小的点 p0；
 19 （2）以 p0 为源点，变换 S-{p0}中所有点的坐标；
 20 （3）以 p0 为源点，计算 S-{p0}中所有点的幅角；
 21 （4）以幅角的非降排序 S-{p0}中所有的点，令事件调度点 T={p1,p2,…,  pn-1}是排序过的数组。
 22 （5）初始化堆栈：令 CHS[0]=pn-1，CHS[1]=p0；令堆栈指针 sp=1，事件调度点数组T的下标 k＝0。
 23 （6）如果 k<n-1，转步骤（7）；否则，算法结束。
 24 （7）计算CHS[sp - 1],CHS[sp] = p0,T[k]所构成的三角区负号D，所
 25 D>=0，sp = sp + 1，CHS[sp] = T[k]，k = k + 1，转步骤（6）；否则，sp = sp - 1，转步骤（6）。
 26 
 27 问题描述
 28 某大学 ACM 集训队，不久前向学校申请了一块空地，成为自己的果园。全体队员兴
 29 高采烈的策划方案，种植了大批果树，有梨树、桃树、香蕉……。后来，发现有些坏蛋，
 30 他们暗地里偷摘果园的果子，被 ACM 集训队队员们发现了。因此，大家商量解决办法，
 31 有人提出：修筑一圈篱笆，把果园围起来，但是由于我们的经费有限，必须尽量节省资金，
 32 所以，我们要找出一种最合理的方案。由于每道篱笆，无论长度多少，都是同等价钱。所
 33 以，大家希望设计出来的修筑一圈篱笆的方案所花费的资金最少。有人已经做了准备工作，
 34 统计了果园里所有果树的位置，每棵果树分别用二维坐标来表示，进行定位。现在，他们
 35 要求全体队员，每人给出一个最合理的方案，来解决修筑篱笆所遇到的困难。要求根据所
 36 有的果树的位置，找出一个 n 边形的最小篱笆，使得所有果树都包围在篱笆内部，或者在
 37 篱笆边沿上。
 38 
 39 输入：
 40 每行有 2n+1 个整数，第一个为 n，表示果园里面共有n 棵果树，接着2n个数，分别成对
 41 的表示每棵果树pi(xi,yi)的位置，(x1,y1)，(x2,y2)，...，(xn,yn),3 <= n <= 100，其中，
 42 -100 <= xi,yi <= 100
 43 
 44 输出：
 45 把设计出来最小 n 边形篱笆的 n 个顶点坐标按逆时针的顺序输出，每个坐标用空格分
 46 开，每个坐标的格式为“(x,y)”。注意，第一个顶点，必须是所有顶点中最低、最左的点。
 47 
 48 输入样例：
 49 5    -1    -1    4    3    1    1    0    3    4    0
 50 
 51 输出样例：
 52 （-1，-1） （4，0） （4，3） （0，3）
 53 */
 54 
 55 #include <iostream>
 56 #include <algorithm>
 57 #include <cmath>
 58 #include <vector>
 59 using namespace std;
 60 
 61 struct Point
 62 {
 63     int x;
 64     int y;
 65 };
 66 
 67 Point p[101];
 68 Point min_ld;
 69 int n;
 70 Point result[101];
 71 
 72 //求出两个点的距离
 73 double Distance( const Point &a, const Point &b )
 74 {
 75     return sqrt((double)(  (a.x  -  b.x) * (a.x  -  b.x ) + (a.y  -  b.y) * (a.y  -  b.y) ) );
 76 }
 77 
 78 ///求叉积
 79 int Cross( const Point &s, const Point &p, const Point &q )// sp, sq
 80 { 
 81     Point sp , sq;
 82     sp.x = p.x - s.x;
 83     sp.y = p.y - s.y;
 84     sq.x = q.x - s.x;
 85     sq.y = q.y - s.y;
 86     return (sp.x * sq.y - sp.y * sq.x);
 87 }
 88 
 89 bool Cmp( const Point &a, const Point &b )
 90 { 
 91     double d1 = Distance( a, min_ld );
 92     double d2 = Distance( min_ld, b );
 93     if( d1 < 1e-10 || d2 < 1e-10 )
 94         return d1 < d2;
 95 
 96     double cos1 = ((double)(a.x - min_ld.x))/ d1;
 97     double cos2 = ((double)(b.x - min_ld.x))/ d2;
 98     if( fabs( cos1 - cos2 ) < 1e-10 )
 99         return d1 < d2;
100     else
101         return cos1 > cos2;
102 }
103 int main()
104 {
105     int k;
106     int top;
107     while( cin >> n )
108     {
109         for(int i = 0; i < n; i++ )
110         {
111             cin >> p[i].x >> p[i].y; 
112         }
113         k = 0;
114         for(int i = 1; i < n; i++ )
115         {
116             if( (p[i].y < p[k].y ) || ( p[i].y == p[k].y && p[i].x <p[k].x ) )
117             {
118                 k = i;
119             }
120         }
121         swap( p[0], p[k] );
122         sort( p + 1, p + n, Cmp ); 
123         //cout << '(' << p[0].x << ',' << p[0].y << ')';
124         //for( i = 1; i < n; i++ )
125         //     cout << ' ' << '(' << p[i].x << ',' << p[i].y << ')';
126         //cout << endl;
127         result[0] = p[0];
128         result[1] = p[1];
129         //result[2] = p[2];
130         top = 1;
131         for(int i = 2; i < n; i++ )
132         {
133             while( top > 0 && Cross( result[top], result[top -  1], p[i] ) >= 0 )
134                 --top;
135             result[++top] = p[i];
136         }
137         cout << '(' << result[0].x << ',' << result[0].y << ')';
138         for(int i = 1; i <= top; i++ )
139             cout << ' ' << '(' << result[i].x << ',' << result[i].y << ')';
140         cout << endl;
141     }
142     return 0;
143 }