May the force be with you!
posts - 52,  comments - 33,  trackbacks - 0


这个题目是老题了,是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)AB 两点可由长方体表面的折线连接,求出A B 的最短表面距离。

LWH 和点的坐标都是整数,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 == 0return 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 == 0return 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 == 0return 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 == -1break;
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 阅读(1408) 评论(3)  编辑 收藏 引用 所属分类: Problem Solving

FeedBack:
# re: 【几何】昨天我水过去的A题[未登录]
2008-01-28 10:14 | Felicia
你把Sherlock的名字写错啦  回复  更多评论
  
# re: 【几何】昨天我水过去的A题
2008-02-13 08:37 | R2@whuacm
@Felicia
嗯,改过来了~~  回复  更多评论
  
# re: 【几何】昨天我水过去的A题
2011-06-06 15:45 | Zheng Gao
通用公式推导的不对,有些情况没考虑到
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


你是第 free hit counter 位访客




<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(4)

随笔分类(54)

随笔档案(52)

文章档案(1)

ACM/ICPC

技术综合

最新随笔

搜索

  •  

积分与排名

  • 积分 - 61528
  • 排名 - 357

最新评论

阅读排行榜

评论排行榜