- 浏览: 35881 次
文章分类
- 全部博客 (41)
- 卧鸟个去 (2)
- Transform (2)
- Mathmatic (9)
- Plant-Tree (7)
- Data-Struct (12)
- Red-Black-Tree (1)
- Radix-Tree (1)
- Trie (2)
- String (4)
- BST (2)
- Amazing-Union-Find-Set (1)
- HDU (27)
- OJ (32)
- BFS (3)
- Pretty-Suffix-Array (2)
- POJ (6)
- Graceful-Segment-Tree (2)
- Geometry (6)
- Priority-Queue (2)
- Dynamic-Programing (1)
- DP (3)
- LCS (1)
- Convex-Hull (2)
- Triangulation (1)
- DFS (3)
- Combinatorial-Mathematics (2)
- Big-Number (1)
- Statistic (3)
- STL (1)
- Shortest-Path (3)
- ZOJ (1)
- Leftist-Tree (1)
- Prime (1)
- Binary-Index-Tree (1)
- (1)
- Stack (1)
- SPFA (0)
- CRT (1)
Surround the Trees
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3223 Accepted Submission(s): 1230
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.
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.
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
Recommend
Ignatius.L
凸包水题直接GramhamScan可以过,不过要注意n < 3两个特例。
果断贴代码:
4285845 | 2011-07-29 12:51:30 | Accepted | 1392 | 78MS | 272K | 1631 B | C++ | 10SGetEternal{(。)(。)}! |
#include <iostream> #include <vector> #include <cmath> #include <cstdlib> #include <algorithm> using namespace std; #define MAXI 111 class point { public : double x, y; point(double tx = 0.0, double ty = 0.0) { x = tx; y = ty; } double dis() { return sqrt(pow(x, 2) + pow(y, 2)); }; point operator - (point &o) { return point(x - o.x, y - o.y); } double operator * (point &o) { return x * o.y - y * o.x; } }ps[MAXI]; vector<point> chul; int n; bool cmp(point &a, point &b) { double cp = (ps[0] - a) * (b - a); if (cp == 0) return (a - ps[0]).dis() > (b - ps[0]).dis(); else if (cp < 0) return 1; return 0; } double GHS() { int i, idm; double tsu = 0.0; for (idm = i = 0; i < n; i++) if (ps[i].y == ps[idm].y && ps[i].x < ps[idm].x || ps[i].y < ps[idm].y) idm = i; swap(ps[idm], ps[0]); sort(ps + 1, ps + n, cmp); chul.clear(); chul.push_back(ps[0]); chul.push_back(ps[1]); for (i = 2; (ps[0] - ps[1]) * (ps[i] - ps[1]) == 0; i++); chul.push_back(ps[i]); for (i++; i < n; i++) { while ((chul[chul.size() - 2] - chul[chul.size() - 1]) * (ps[i] - chul[chul.size() - 1]) >= 0) chul.pop_back(); chul.push_back(ps[i]); } for (i = 0; i < chul.size(); i++) tsu += (chul[(i + 1) % chul.size()] - chul[i]).dis(); return tsu; } int main() { int i; while (scanf("%d", &n), n) { for (i = 0; i < n; i++) scanf("%lf%lf", &ps[i].x, &ps[i].y); if (n == 2) printf("%.2lf\n", ps[1] - ps[0]); else if (n == 1) printf("0\n"); else printf("%.2lf\n", GHS()); } return 0; }
Thanks……
发表评论
-
HDU 1370 Biorhythms
2011-08-03 10:27 1146Biorhythms Time Limit: 2000/10 ... -
HDU 1075 What Are You Talking About
2011-08-04 11:00 829What Are You Talking About Tim ... -
HDU 1058 Humble Numbers
2011-08-02 15:55 1166Humble Numbers Time Limit: 200 ... -
HDU 2095 find your present (2)
2011-08-02 16:13 760find your present (2) Time Lim ... -
HDU 1022 Train Problem I
2011-08-02 21:00 991Train Problem I Time Limit: 20 ... -
2142 HDU box
2011-08-02 21:21 731box Time Limit: 3000/1000 MS ( ... -
HDU 2151 Worm
2011-08-01 20:48 781Worm Time Limit: 1000/1000 MS ... -
HDU 2722 Here We Go(relians) Again
2011-08-02 00:06 964Here We Go(relians) Again Time ... -
HDU 3791 二叉搜索树
2011-08-02 14:26 1157二叉搜索树 Time Limit: 20 ... -
PKU 2352 Stars
2011-07-31 21:47 980Stars Time Limit: 1000MS ... -
PKU 2774 Long Long Message
2011-07-31 21:26 858Long Long Message Time Li ... -
PKU 2777 Count Color
2011-07-31 21:31 765Count Color Time Limit: 1 ... -
HDU 2098 分拆素数和
2011-07-31 21:08 1010分拆素数和 Time Limit: 1000/1000 MS ... -
ZOJ 3512 Financial Fraud .
2011-07-31 20:49 1224Financial Fraud Time Limit: 3 ... -
HDU 1798 Tell me the area .
2011-07-31 20:47 1065Tell me the area Time Limit: 3 ... -
HDU 2962 Trucking .
2011-07-31 20:46 637Trucking Time Limit: 20000/100 ... -
HDU 1596 find the safest road .
2011-07-31 20:45 569find the safest road Time Limi ... -
HDU 2553 N皇后问题 .
2011-07-31 20:20 658N皇后问题 Time Limit: 2000/1000 MS ... -
HDU 1234 开门人和关门人 .
2011-07-31 20:17 639开门人和关门人 Time Limit: 2000/1000 ... -
HDU 1174 爆头 .
2011-07-31 20:16 581爆头 Time Limit: 2000/1000 M ...
相关推荐
HDU 里面的2000~2099道题目的源码。谢谢支持
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.
杭电acm 一些java语言实现的水题目
杭电ACM2000-2099题的解题报告
杭电选课插件
凸包经典入门,求凸包周长.00000000000000000000000
HDU的一题........HDU DP动态规
ACM HDU题目分类,我自己总结的大概只有十来个吧
算术(HDU-6715).rar
杭电操作系统实验 HDU操作系统实验.zip
最短路(HDU-2544).rar