- 浏览: 37565 次
文章分类
- 全部博客 (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 1192Biorhythms Time Limit: 2000/10 ... -
HDU 1075 What Are You Talking About
2011-08-04 11:00 866What Are You Talking About Tim ... -
HDU 1058 Humble Numbers
2011-08-02 15:55 1223Humble Numbers Time Limit: 200 ... -
HDU 2095 find your present (2)
2011-08-02 16:13 817find your present (2) Time Lim ... -
HDU 1022 Train Problem I
2011-08-02 21:00 1013Train Problem I Time Limit: 20 ... -
2142 HDU box
2011-08-02 21:21 763box Time Limit: 3000/1000 MS ( ... -
HDU 2151 Worm
2011-08-01 20:48 849Worm Time Limit: 1000/1000 MS ... -
HDU 2722 Here We Go(relians) Again
2011-08-02 00:06 1026Here We Go(relians) Again Time ... -
HDU 3791 二叉搜索树
2011-08-02 14:26 1208二叉搜索树 Time Limit: 20 ... -
PKU 2352 Stars
2011-07-31 21:47 1027Stars Time Limit: 1000MS ... -
PKU 2774 Long Long Message
2011-07-31 21:26 903Long Long Message Time Li ... -
PKU 2777 Count Color
2011-07-31 21:31 795Count Color Time Limit: 1 ... -
HDU 2098 分拆素数和
2011-07-31 21:08 1062分拆素数和 Time Limit: 1000/1000 MS ... -
ZOJ 3512 Financial Fraud .
2011-07-31 20:49 1283Financial Fraud Time Limit: 3 ... -
HDU 1798 Tell me the area .
2011-07-31 20:47 1124Tell me the area Time Limit: 3 ... -
HDU 2962 Trucking .
2011-07-31 20:46 684Trucking Time Limit: 20000/100 ... -
HDU 1596 find the safest road .
2011-07-31 20:45 605find the safest road Time Limi ... -
HDU 2553 N皇后问题 .
2011-07-31 20:20 703N皇后问题 Time Limit: 2000/1000 MS ... -
HDU 1234 开门人和关门人 .
2011-07-31 20:17 674开门人和关门人 Time Limit: 2000/1000 ... -
HDU 1174 爆头 .
2011-07-31 20:16 612爆头 Time Limit: 2000/1000 M ...
相关推荐
杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU...
HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-...
【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...
【HDU-GO v19.1225.2.zip】是一个针对杭州电子科技大学(HDU)选课系统的浏览器插件,版本号为v19.1225.2。这个插件的主要功能是优化和提升学生在进行网络选课时的体验,它可能包含了增强界面、自动化操作、数据解析...
【标题】"HDU-ACM_java.rar" 是一个针对杭州电子科技大学(HDU)ACM竞赛的资源压缩包,其中包含的是使用Java语言编写的算法解决方案。这个压缩包主要面向那些参与或准备参与ACM国际大学生程序设计竞赛(ICPC)的参赛...
【标题】"HDU-2000-2099.zip_hdu2000" 是一个包含杭电(Hangzhou Dianzi University)ACM竞赛题目解题报告的压缩包,覆盖了编号从2000到2099的题目。这个资源对于学习算法、提高编程技巧以及准备ACM/ICPC(国际大学...
HDU(杭州电子科技大学在线评测系统)是一个知名的编程竞赛平台,为编程爱好者提供了大量的算法题目进行练习和比赛。这个名为"HDU-2000-2099.rar_hdu"的压缩包包含了该平台从2000到2099共100道题目的源代码。这些...
凸包经典入门,求凸包周长.00000000000000000000000
个人数据库原理课程设计的期末作业留档_HDU-suspermarket_sys
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
这个压缩文件包含的是作者个人提交并解决的ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)题目,这些题目来源于HDU的在线编程平台。 【描述】"杭电的一些acm题目,都是我自己一个一...
标题中的"hdu5102.zip_K."暗示这是一个与编程竞赛相关的题目,通常在HDU(杭州电子科技大学)在线判题系统中出现。这个题目可能是一个编程挑战,要求参赛者解决一个特定的问题,并提交源代码以供自动评判。"K."可能...
HDU-ACM课件.rar 是一个专门为编程竞赛爱好者准备的资源包,主要涵盖了ACM(国际大学生程序设计竞赛)中常见的算法知识。这个压缩包包含了一系列与算法相关的主题,旨在帮助初学者理解和掌握基础及进阶算法。下面将...