這個題目是老題了，是Northeastern Europe 1996的題目 ，也就是POJ1444。
題目地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1444
這個解法是錯的?。。?！比賽時數據菜，水過去了～～～
具體解法看Felicia的：http://www.shnenglu.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 閱讀(1465)
評論(3) 編輯 收藏 引用 所屬分類:
Problem Solving