这个题目是老题了，是Northeastern Europe 1996的题目 ，也就是POJ1444。
题目地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1444
这个解法是错的！！！！比赛时数据菜，水过去了～～～
具体解法看Felicia的：http://www.cppblog.com/Felicia/archive/2008/01/23/41747.html
【题目描述】
Problem A－最短表面距离
by littlekid
Description
一个长方体P={ (x,y,z) | 0<=x<=L,
0<=y<=w, 0<=z<=H }，长方体表面有任意两点
A(x1,y1,z1)和B(x2,y2,z2)，A、B 两点可由长方体表面的折线连接，求出A 和B 的最短表面距离。
L、W、H 和点的坐标都是整数，0<=L,W,H<=1000。
Input
输入数据有多组，每组包含三行，格式如下：
L W H
x1 y1 z1
x2 y2 z2
输入以一行“-1 -1 -1”结束。
Output
对于每组输入数据输出一行，输出最短表面距离，要求四舍五入倒小数点后两位。
Sample Input
5 5 2
3 1 2
3 5 0
-1 -1 -1
Sample Output
6.00
【相关知识】
立体几何空间概念、平面几何求距离、两点间最短距离。
【解题分析】
这种题目原来上数学课的时候做过，不过自己写一个通用的程序就不怎么简单了。我当时没怎么想，觉得就用数学方法，枚举各种情况，一一处理就好了（Sherock就是用的这个方法，而且推出了公式，代码超级牛）。不过我不怎么擅长推公式，而且我比赛的时候推公式是一般会错的（后来证明我写代码也容易错）。
最后我用的方法非常朴实：对长方体分三种方式（前->上->后->下，前->右->后->左，下->右->上->左）展开，然后在每种展开情况下求平面最短距离（如果两个点有一个以上不在展开平面内：对于两点，有两种连线方式（想象一下，可以从一个点顺时针或逆时针到另一个点）。
【解题思路】
我的思路是：分别从三个方向（前->上->后->下，前->右->后->左，下->右->上->左），将长方体展开，如果两个点都在这些面，分两种情况求两点间距离，否则返回一个很大的数值。所有求得值得最小值就是解（怎么证明？）。
【测试数据】
我个人认为这个题必须设计以下数据（特别是对于我的程序的数据）：
1、两个点在一个面（六个面六组）；
2、两个点在相邻面（八组）；
3、相对面的两点（三组）；
4、在两个面相交的地方的点的情况，三个面相交的点的情况（很多组，而且测试数据中肯定有不少这样的数据）。
【解题总结】
当时我较快就想出了思路，然后没写，去吃午饭得时候我向Felicia他们说了下自己得思路，他们没听懂。回来后写code，代码非常臃肿，结果复制得原因，我有一个函数忘记改调一个地方，好在后面通过数据找出来了，WA了三次。
【程序代码】
下面是我当时的代码，很臃肿，可以优化很多，在这里给大家笑话！！！大家自己写好点的代码吧（我过一段时间再贴优化代码）
1 # include <iostream>
2 # include <cmath>
3 using namespace std;
4
5 const int MAX = 0x7fffffff;
6
7 int L, W, H;
8 int xx1, xx2, yy1, yy2, zz1, zz2;
9 double ans;
10
11 bool in_field_1_2(int xx, int yy, int zz)
12 {
13 if ((yy == W || yy == 0) && (zz < H && zz > 0) && (xx > 0 && xx < L)) return true;
14 // cout << "not in field 1/2" << endl; ///
15 return false;
16 }
17
18 bool in_field_3_4(int xx, int yy, int zz)
19 {
20 if ((zz == H || zz == 0) && (xx < L && xx > 0) && (yy > 0 && yy < W)) return true;
21 // cout << "not in field 3/4" << endl; ///
22 return false;
23 }
24
25 bool in_field_5_6(int xx, int yy, int zz)
26 {
27 if ((xx == L || xx == 0) && (zz < H && zz > 0) && (yy > 0 && yy < W)) return true;
28 // cout << "not in field 5/6" << endl; ///
29 return false;
30 }
31
32 bool in_field_1(int xx, int yy, int zz)
33 {
34 if (yy == 0) return true;
35 // cout << "not in field 1" << endl; ///
36 return false;
37 }
38
39 bool in_field_2(int xx, int yy, int zz)
40 {
41 if (yy == W) return true;
42 // cout << "not in field 2" << endl; ///
43 return false;
44 }
45
46 bool in_field_3(int xx, int yy, int zz)
47 {
48 if (zz == 0) return true;
49 // cout << "not in field 3" << endl; ///
50 return false;
51 }
52
53 bool in_field_4(int xx, int yy, int zz)
54 {
55 if (zz == H) return true;
56 // cout << "not in field 4" << endl; ///
57 return false;
58 }
59 bool in_field_5(int xx, int yy, int zz)
60 {
61 if (xx == 0) return true;
62 // cout << "not in field 5" << endl; ///
63 return false;
64 }
65
66 bool in_field_6(int xx, int yy, int zz)
67 {
68 if (xx == L) return true;
69 // cout << "not in field 6" << endl; ///
70 return false;
71 }
72
73 double cal_1()
74 {
75 if (in_field_5_6(xx1, yy1, zz1)) return MAX;
76 if (in_field_5_6(xx2, yy2, zz2)) return MAX;
77
78 int xxxx1 = xx1, xxxx2 = xx2, zzzz1, zzzz2;
79 if (in_field_1(xx1, yy1, zz1))
80 {
81 zzzz1 = zz1;
82 }
83 else if (in_field_4(xx1, yy1, zz1))
84 {
85 zzzz1 = H + yy1;
86 }
87 else if (in_field_2(xx1, yy1, zz1))
88 {
89 zzzz1 = H+W+(H-zz1);
90 }
91 else
92 {
93 zzzz1 = H+W+H+(W-yy1);
94 }
95
96
97 if (in_field_1(xx2, yy2, zz2))
98 {
99 zzzz2 = zz2;
100 }
101 else if (in_field_4(xx2, yy2, zz2))
102 {
103 zzzz2 = H+yy2;
104 }
105 else if (in_field_2(xx2, yy2, zz2))
106 {
107 zzzz2 = H+W+(H-zz2);
108 }
109 else
110 {
111 zzzz2 = H+W+H+(W-yy2);
112 }
113
114 int tmp;
115 if (zzzz2 < zzzz1)
116 {
117 tmp = zzzz1;
118 zzzz1 = zzzz2;
119 zzzz2 = tmp;
120 }
121
122 // cout << "cal 1-----------" << endl;///
123 // cout << xxxx1 << " " << zzzz1 << endl;///
124 // cout << xxxx2 << " " << zzzz2 << endl;///
125
126 int dis1 = (zzzz2 - zzzz1)*(zzzz2-zzzz1) + (xxxx2 - xxxx1)*(xxxx2-xxxx1);
127 int dis2 = (H+W+H+W+zzzz1 - zzzz2)*(H+W+H+W+zzzz1 - zzzz2) + (xxxx2 - xxxx1)*(xxxx2-xxxx1);
128
129 if (dis2 < dis1) dis1 = dis2;
130
131 return sqrt(dis1);
132 }
133
134 double cal_2()
135 {
136 if (in_field_3_4(xx1, yy1, zz1)) return MAX;
137 if (in_field_3_4(xx2, yy2, zz2)) return MAX;
138
139 int xxxx1, xxxx2, zzzz1 = zz1, zzzz2 = zz2;
140 if (in_field_1(xx1, yy1, zz1))
141 {
142 xxxx1 = xx1;
143 }
144 else if (in_field_6(xx1, yy1, zz1))
145 {
146 xxxx1 = L + yy1;
147 }
148 else if (in_field_2(xx1, yy1, zz1))
149 {
150 xxxx1 = L + W + (L - xx1);
151 }
152 else
153 {
154 xxxx1 = L+W+L+(W-yy1);
155 }
156
157
158 if (in_field_1(xx2, yy2, zz2))
159 {
160 xxxx2 = xx2;
161 }
162 else if (in_field_6(xx2, yy2, zz2))
163 {
164 xxxx2 = L + yy2;
165 }
166 else if (in_field_2(xx2, yy2, zz2)) // WA!!!
167 {
168 xxxx2 = L + W + (L - xx2);
169 }
170 else
171 {
172 xxxx2 = L+W+L+(W-yy2);
173 }
174
175 int tmp;
176 if (xxxx2 < xxxx1)
177 {
178 tmp = xxxx1;
179 xxxx1 = xxxx2;
180 xxxx2 = tmp;
181 }
182
183 // cout << "cal 2-----------" << endl;///
184 // cout << zzzz1 << " " << xxxx1 << endl;///
185 // cout << zzzz2 << " " << xxxx2 << endl;///
186
187 int dis1 = (xxxx2 - xxxx1)*(xxxx2-xxxx1) + (zzzz2 - zzzz1)*(zzzz2-zzzz1);
188 int dis2 = (L+W+L+W+xxxx1 - xxxx2)*(L+W+L+W+xxxx1 - xxxx2) + (zzzz2 - zzzz1)*(zzzz2-zzzz1);
189
190 if (dis2 < dis1) dis1 = dis2;
191 return sqrt(dis1);
192 }
193
194 double cal_3()
195 {
196 if (in_field_1_2(xx1, yy1, zz1)) return MAX;
197 if (in_field_1_2(xx2, yy2, zz2)) return MAX;
198
199 int yyyy1 = yy1, yyyy2 = yy2, xxxx1, xxxx2;
200 if (in_field_3(xx1, yy1, zz1))
201 {
202 xxxx1 = xx1;
203 }
204 else if (in_field_6(xx1, yy1, zz1))
205 {
206 xxxx1 = L + zz1;
207 }
208 else if (in_field_4(xx1, yy1, zz1))
209 {
210 xxxx1 = L+H+(L-xx1);
211 }
212 else
213 {
214 xxxx1 = L+H+L+(H-zz1);
215 }
216
217
218 if (in_field_3(xx2, yy2, zz2))
219 {
220 xxxx2 = xx2;
221 }
222 else if (in_field_6(xx2, yy2, zz2))
223 {
224 xxxx2 = L + zz2;
225 }
226 else if (in_field_4(xx2, yy2, zz2))
227 {
228 xxxx2 = L+H+(L-xx2);
229 }
230 else
231 {
232 xxxx2 = L+H+L+(H-zz2);
233 }
234
235 int tmp;
236 if (xxxx2 < xxxx1)
237 {
238 tmp = xxxx1;
239 xxxx1 = xxxx2;
240 xxxx2 = tmp;
241 }
242
243 // cout << "cal 3-----------" << endl;///
244 // cout << yyyy1 << " " << xxxx1 << endl;///
245 // cout << yyyy2 << " " << xxxx2 << endl;///
246
247 int dis1 = (xxxx2 - xxxx1)*(xxxx2-xxxx1) + (yyyy2 - yyyy1)*(yyyy2-yyyy1);
248 int dis2 = (L+H+L+H+xxxx1 - xxxx2)*(L+H+L+H+xxxx1 - xxxx2) + (yyyy2 - yyyy1)*(yyyy2-yyyy1);
249
250 if (dis2 < dis1) dis1 = dis2;
251 return sqrt(dis1);
252 }
253
254 int main()
255 {
256 double tmp;
257 while (true)
258 {
259 scanf("%d %d %d", &L, &W, &H);
260 if (L == -1 && W == -1 && H == -1) break;
261 ans = MAX;
262 scanf("%d %d %d", &xx1, &yy1, &zz1);
263 scanf("%d %d %d", &xx2, &yy2, &zz2);
264 tmp = cal_1();
265 // cout << "tmp = " << tmp << endl; ///
266 if (tmp < ans) ans = tmp;
267 tmp = cal_2();
268 // cout << "tmp = " << tmp << endl; ///
269 if (tmp < ans) ans = tmp;
270 tmp = cal_3();
271 // cout << "tmp = " << tmp << endl; ///
272 if (tmp < ans) ans = tmp;
273
274 printf("%.2lf\n", ans);
275 }
276 return 0;
277 }
278
下面是Sherlock的代码，思路跟我的差不多，不过他推了公式，然后代码比我的简单多了。
1 /*
2 已知立方体长宽高分别为L、W、H，给定立方体上两个点(a, b, c), (x, y, z)(x, a <= L, y, b <= W, z, c <= H)
3 求该两点间的最短距离
4 */
5
6 #include<iostream>
7 #include<cmath>
8
9 using namespace std;
10
11 int l, w, h, a, b, c, x, y, z;
12 double ans;
13
14 double f(int x)
15 {
16 return ((x + 0.0) * (x + 0.0));
17 }
18
19 void count1()
20 {
21 ans = sqrt(f(a - x) + f(b - y) + f(c - z) + 0.0);
22 }
23
24 void count2()
25 {
26 double ans1, ans2;
27 if (b == 0 || b == w)
28 {
29 ans1 = sqrt(min(f(h - z + w + h - c), f(z + w + c)) + f(x - a));
30 ans2 = sqrt(min(f(l - x + w + l - a), f(x + w + a)) + f(c - z));
31 }
32 else
33 if (a == 0 || a == l)
34 {
35 ans1 = sqrt(min(f(w - y + l + w - b), f(y + l + b)) + f(c - z));
36 ans2 = sqrt(min(f(h - z + l + h - c), f(z + l + c)) + f(b - y));
37 }
38 else
39 {
40 ans1 = sqrt(min(f(w - y + h + w - b), f(y + h + b)) + f(x - a));
41 ans2 = sqrt(min(f(l - x + h + l - a), f(x + h + a)) + f(b - y));
42 }
43 ans = min(ans1, ans2);
44 }
45
46 void count3()
47 {
48 if (a == 0 || a == l)
49 {
50 if (y == 0 || y == w)
51 ans = sqrt((f(abs(x - a) + abs(b - y)) + f(c - z)) + 0.0);
52 else
53 ans = sqrt((f(abs(z - c) + abs(x - a)) + f(b - y)) + 0.0);
54 }
55 else
56 if (b == 0 || b == w)
57 {
58 if (x == 0 || x == l)
59 ans = sqrt((f(abs(x - a) + abs(b - y)) + f(c - z)) + 0.0);
60 else
61 ans = sqrt((f(abs(c - z) + abs(b - y)) + f(a - x)) + 0.0);
62 }
63 else
64 {
65 if (x == 0 || x == l)
66 ans = sqrt((f(abs(c - z) + abs(x - a)) + f(b - y)) + 0.0);
67 else
68 ans = sqrt((f(abs(c - z) + abs(b - y)) + f(a - x)) + 0.0);
69 }
70 }
71
72 int main()
73 {
74 while (scanf("%d%d%d", &l, &w, &h) != -1)
75 {
76 if (l == -1 && w == -1 && h == -1)
77 break;
78 scanf("%d%d%d%d%d%d", &a, &b, &c, &x, &y, &z);
79 if ((a == x && (a == 0 || a == l)) || (b == y && (b == 0 || b == w)) || (c == z && (c == 0 || c == h)))
80 count1();
81 else
82 if ((a == 0 && x == l) || (b == 0 && y == w) || (c == 0 && z == h) || (a == l && x == 0) || (b == w && y == 0) || (c == h && z == 0))
83 count2();
84 else
85 count3();
86 printf("%.2lf\n", ans);
87 }
88 }
89
posted on 2008-01-23 10:03
R2 阅读(1425)
评论(3) 编辑 收藏 引用 所属分类:
Problem Solving