首页 > 代码库 > HDU 4573 Throw the Stones（动态三维凸包）（2013 ACM-ICPC长沙赛区全国邀请赛）
HDU 4573 Throw the Stones（动态三维凸包）（2013 ACM-ICPC长沙赛区全国邀请赛）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4573
Problem Description
Remember our childhood? A few naked children throw stones standing on the same position, the one throws farther win the game. Aha, of course, there are some naughty boys who care more about whether they can urinate father.
You believe it or not, anyway, I believed. Nowadays, some of the children are smarter than we were, while others may be more naughty.
A week ago, I saw several children throw stones. In fact, they are more clever than we were, since the game they played, apparently, is more complex than we did. Maybe you have different points of view, however, you’d better learn about the rules of the game before expressing your views. A group of children take turns to throw stones standing on the same position. After some child throw a stone, the children will draw a convex polyhedron with smallest volume together to enclose all the stones thrown by them. You may assume that the stone is so small as to be abstracted as a point in three-dimensional space. Naively, the children regard the space enclosed by the convex polyhedron as territory under their control. After a child throw his stone, the score he obtains equals the incremental of the volume of their territory. Unfortunately, the first three child’s score will always be zero. At last, the child with the highest score will win the game, and known as the "King".
I think you have accepted my opinion already, for the rules of their throwing stones game are really complicated. But, you also don’t need to be frustrated for it. Now, in order to show you are smarter, maybe you can write a program to help the children point out their "King".
You believe it or not, anyway, I believed. Nowadays, some of the children are smarter than we were, while others may be more naughty.
A week ago, I saw several children throw stones. In fact, they are more clever than we were, since the game they played, apparently, is more complex than we did. Maybe you have different points of view, however, you’d better learn about the rules of the game before expressing your views. A group of children take turns to throw stones standing on the same position. After some child throw a stone, the children will draw a convex polyhedron with smallest volume together to enclose all the stones thrown by them. You may assume that the stone is so small as to be abstracted as a point in three-dimensional space. Naively, the children regard the space enclosed by the convex polyhedron as territory under their control. After a child throw his stone, the score he obtains equals the incremental of the volume of their territory. Unfortunately, the first three child’s score will always be zero. At last, the child with the highest score will win the game, and known as the "King".
I think you have accepted my opinion already, for the rules of their throwing stones game are really complicated. But, you also don’t need to be frustrated for it. Now, in order to show you are smarter, maybe you can write a program to help the children point out their "King".
Input
Input consists of a number of cases. The data of each case appears on a number of input lines, the first of which contains an integer N. The following N lines contain three number (xi, yi, zi) indicating coordinates of the stone thrown by the i-th child.
Note: 1 <= N <= 10^4, 1 <= i <= N, -10^4 <= xi , yi , zi <= 10^4.
Note: 1 <= N <= 10^4, 1 <= i <= N, -10^4 <= xi , yi , zi <= 10^4.
Output
For each test case, you should output two lines. The first line is "Case #K:", K means the number of the test case. The second line is "i v", i means index of the "King" and v means the score of the "King". If there are more than one "King", output the one throws stone earlier than others.
Please round the result to 2 digits after decimal point if necessary.
Please round the result to 2 digits after decimal point if necessary.
题目大意：给一个三维空间点集依次加入N个点，形成一个三维凸包。问加入哪一个点的时候，凸包的体积增量最大，即前 i 个点组成的凸包体积减去前 i - 1个点组成的凸包体积最大。输出这个点，并输出这个增量。
思路：http://blog.csdn.net/catalyst1314/article/details/9017673
PS：我的代码框架几乎都是照着上面写的。但是怎么看内存都会超出限制，虽然不知道为什么实际上没有（我算错了？），虽说现场没有这种限制。然后不知为何说时间复杂度是O(n*sqrt(n))，我怎么觉得最坏情况下还是O(n^2)的……
代码（531MS）：
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cmath> 6 using namespace std; 7 typedef long long LL; 8 9 const int MAXN = 10001; 10 const double EPS = 1e-9; 11 12 inline int sgn(double x) { 13 return (x > EPS) - (x < -EPS); 14 } 15 16 struct Point { 17 double x, y, z; 18 Point() {} 19 Point(double x, double y, double z): x(x), y(y), z(z) {} 20 void read() { 21 scanf("%lf%lf%lf", &x, &y, &z); 22 } 23 Point operator - (const Point &rhs) const { 24 return Point(x - rhs.x, y - rhs.y, z - rhs.z); 25 } 26 double operator * (const Point &rhs) const { 27 return x * rhs.x + y * rhs.y + z * rhs.z; 28 } 29 }; 30 double length(const Point &a) { 31 return sqrt(a * a); 32 } 33 Point cross(const Point &a, const Point &b) { 34 Point res; 35 res.x = a.y * b.z - a.z * b.y; 36 res.y = a.z * b.x - a.x * b.z; 37 res.z = a.x * b.y - a.y * b.x; 38 return res; 39 } 40 Point cross(const Point &o, const Point &a, const Point &b) { 41 return cross(a - o, b - o); 42 } 43 double volume(const Point &a, const Point &b, const Point &c, const Point &d) { 44 return cross(c - a , b - a) * (d - a) / 6; 45 } 46 Point p[MAXN]; 47 48 struct Face { 49 int a, b, c; 50 bool flag; 51 Face() {} 52 Face(int a, int b, int c, bool flag): a(a), b(b), c(c), flag(flag) {} 53 bool can_see(const Point &q) { 54 return sgn(volume(p[a], p[b], p[c], q)) > 0; 55 } 56 }; 57 Face fac[MAXN * 10]; 58 59 struct Convex { 60 double diff_vol; 61 int cnt, mat[MAXN][MAXN]; 62 63 void init() { 64 cnt = 0; 65 for(int i = 0; i < 4; ++i) { 66 Face newf = Face((i + 1) % 4, (i + 2) % 4, (i + 3) % 4, true); 67 if(newf.can_see(p[i])) swap(newf.a, newf.c); 68 mat[newf.a][newf.b] = mat[newf.b][newf.c] = mat[newf.c][newf.a] = cnt; 69 fac[cnt++] = newf; 70 } 71 } 72 73 void restore(int k, int a, int b) { 74 int f = mat[a][b]; 75 if(fac[f].flag) { 76 if(fac[f].can_see(p[k])) dfs(k, f); 77 else { 78 mat[b][a] = mat[a][k] = mat[k][b] = cnt; 79 fac[cnt++] = Face(b, a, k, true); 80 } 81 } 82 } 83 84 void dfs(int k, int f) { 85 diff_vol += volume(p[fac[f].a], p[fac[f].b], p[fac[f].c], p[k]); 86 fac[f].flag = false; 87 restore(k, fac[f].b, fac[f].a); 88 restore(k, fac[f].c, fac[f].b); 89 restore(k, fac[f].a, fac[f].c); 90 } 91 92 double update(int k) { 93 diff_vol = 0; 94 for(int i = 0; i < cnt; ++i) { 95 if(!fac[i].flag || !fac[i].can_see(p[k])) continue; 96 dfs(k, i); 97 break; 98 } 99 return diff_vol;100 }101 102 double vol() {103 double res = 0;104 for(int i = 0; i < cnt; ++i) if(fac[i].flag)105 res -= volume(p[fac[i].a], p[fac[i].b], p[fac[i].c], Point(0, 0, 0));106 return res;107 }108 } solver;109 110 int n, kase;111 112 void solve() {113 int king = 0;114 double maxans = 0;115 for(int i = 1, tmp = 1; i < n; ++i) {116 if(tmp == 1) {117 tmp += sgn(length(p[0] - p[i]));118 if(tmp > 1) swap(p[1], p[i]);119 } else if(tmp == 2) {120 tmp += sgn(length(cross(p[0], p[1], p[i])));121 if(tmp > 2) swap(p[2], p[i]);122 } else if(tmp == 3) {123 tmp += (sgn(volume(p[0], p[1], p[2], p[i])) != 0);124 if(tmp > 3) {125 swap(p[3], p[i]);126 solver.init();127 for(int j = 4; j <= i; ++j) solver.update(j);128 king = i, maxans = solver.vol();129 }130 } else {131 double v = solver.update(i);132 if(sgn(v - maxans) > 0) {133 maxans = v;134 king = i;135 }136 }137 }138 printf("%d %.2f\n", king + 1, maxans);139 }140 141 int main() {142 while(scanf("%d", &n) != EOF) {143 for(int i = 0; i < n; ++i) p[i].read();144 printf("Case #%d:\n", ++kase);145 solve();146 }147 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。