Surround the Trees
Problem Description
There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know how to calculate it. Can you help him?
The diameter and length of the trees are omitted, which means a tree can be seen as a point. The thickness of the rope is also omitted which means a rope can be seen as a line.
There are no more than 100 trees.
Input
The input contains one or more data sets. At first line of each input data set is number of trees in this data set, it is followed by series of coordinates of the trees. Each coordinate is a positive integer pair, and each integer is less than 32767. Each pair is separated by blank.
Zero at line for number of trees terminates the input for your program.
Output
The minimal length of the rope. The precision should be 10^-2.
Sample Input
9
12 7
24 9
30 5
41 9
80 7
50 87
22 9
45 1
50 7
0
Sample Output
243.06
Source
Asia 1997, Shanghai (Mainland China)
题目类型：求凸包周长
算法分析：使用Jarvis步进法(卷包裹法)求解出构成凸包的点集，然后计算每条边的长度即可，注意若只有一个点，则直接返回0.00。若有两个点，则直接返回两点之间的距离！！！
|
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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 |
/************************************************* Author :supermaker Created Time :2016/1/26 12:27:46 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 166 + 66; int sgn (double val) { if (fabs (val) < EPS) return 0; else if (val < 0) return -1; return 1; } struct Point { double x, y; Point () {} Point (double xx, double yy) : x (xx), y (yy) {} Point operator + (const Point &a) const { return Point (x + a.x, y + a.y); } Point operator - (const Point &a) const { return Point (x - a.x, y - a.y); } double operator ^ (const Point &a) const { return x * a.y - y * a.x; } double operator * (const Point &a) const { return x * a.x + y * a.y; } }; double dist (Point p1, Point p2) { return sqrt ((p2 - p1) * (p2 - p1)); } double CrossMul (Point p0, Point p1, Point p2) { return (p1 - p0) ^ (p2 - p0); } double DotMul (Point p0, Point p1, Point p2) { return (p1 - p0) * (p2 - p0); } Point point[maxn]; int n, start_pos; bool vis[maxn]; int SS (int u) { int pos = -1; for (int i = 1; i <= n; i++) if (i != u && !vis[i]) { if (pos == -1) pos = i; else { double tt1 = CrossMul (point[u], point[i], point[pos]); if (sgn (tt1) == 1) pos = i; else if (sgn (tt1) == 0) { double tt2 = DotMul (point[pos], point[u], point[i]); if (sgn (tt2) == -1) pos = i; } } } vis[pos] = true; return pos; } double Jarvis () { if (n == 1) return 0; else if (n == 2) return dist (point[1], point[2]); else { double res = 0; memset (vis, false, sizeof (vis)); int now = start_pos, next; while (1) { next = SS (now); res += dist (point[now], point[next]); now = next; if (now == start_pos) break; } return res; } } int main() { //CFF; //CPPFF; while (scanf ("%d", &n) != EOF) { if (n == 0) break; start_pos = -1; Point start = Point (INF, INF); for (int i = 1; i <= n; i++) { double x, y; scanf ("%lf%lf", &x, &y); point[i] = Point (x, y); if (sgn (point[i].x - start.x) == -1) start = point[i], start_pos = i; else if (sgn (point[i].x - start.x) == 0 && sgn (point[i].y - start.y) == -1) start = point[i], start_pos = i; } printf ("%.2lf\n", Jarvis ()); } return 0; } |
- « 上一篇：poj3304
- poj1113：下一篇 »