|
|
Posted on 2008-10-06 22:05 Hero 閱讀(116) 評論(0) 編輯 收藏 引用 所屬分類: 代碼如詩－－ACM
1 /*
2 ID: wangzha4
3 LANG: C++
4 TASK: fence3
5 */
6
7 /*迭代--模擬退火
8 Executing
9 Test 1: TEST OK [0.011 secs, 2716 KB]
10 Test 2: TEST OK [0.011 secs, 2716 KB]
11 Test 3: TEST OK [0.011 secs, 2716 KB]
12 Test 4: TEST OK [0.000 secs, 2720 KB]
13 Test 5: TEST OK [0.011 secs, 2720 KB]
14 Test 6: TEST OK [0.022 secs, 2720 KB]
15 Test 7: TEST OK [0.000 secs, 2716 KB]
16 Test 8: TEST OK [0.011 secs, 2716 KB]
17 Test 9: TEST OK [0.000 secs, 2716 KB]
18 Test 10: TEST OK [0.000 secs, 2716 KB]
19 Test 11: TEST OK [0.000 secs, 2720 KB]
20 Test 12: TEST OK [0.011 secs, 2716 KB]
21 */
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <math.h>
25
26 const int itimes =50 ;
27 const int size = 160 ;
28 const double change = 30 ;
29
30 struct Point
31 {
32 int x ;
33 int y ;
34 };
35 struct Point sn[size], en[size] ;
36
37 const int xdir[4] = { 0, 1, 0, -1 } ;
38 const int ydir[4] = { 1, 0, -1, 0 } ;//xy方向
39
40 int inn ;
41 double ansx ; double ansy ;
42 double bestdist ;
43
44 void swap( int &a, int &b )
45 {
46 int temp = a ; a = b ; b = temp ;
47 }
48
49 double fmin( double a, double b )
50 {
51 return a < b ? a : b ;
52 }
53
54 double fdist( double x1, double y1, double x2, double y2 )
55 {
56 return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ) ;
57 }
58
59 void input()
60 {
61 for( int i=1; i<=inn; i++ )
62 {
63 scanf( "%d %d", &sn[i].x, &sn[i].y ) ;
64 scanf( "%d %d", &en[i].x, &en[i].y ) ;
65 if( sn[i].x > en[i].x ) swap( sn[i].x, en[i].x ) ;
66 if( sn[i].y > en[i].y ) swap( sn[i].y, en[i].y ) ;
67 }
68 }
69
70 double comdist( double x, double y )
71 {
72 double reval = 0 ;
73 for( int i=1; i<=inn; i++ )
74 {
75 if( x>sn[i].x && x<en[i].x ) reval += fabs( y-sn[i].y ) ;
76 else if( y>sn[i].y && y<en[i].y ) reval += fabs( x-sn[i].x ) ;
77 else reval += fmin( fdist(x,y,sn[i].x,sn[i].y), fdist(x,y,en[i].x,en[i].y) ) ;
78 }
79
80 return reval ;
81 }
82
83 void process()
84 {
85 ansx = ansy = 0 ;//初始化節點坐標為(0, 0)
86 double xchange = change ; double ychange = change ;//初始化迭代量為20
87 bestdist = comdist( ansx, ansy ) ; int bestdir = -1 ;
88
89 for( int i=1; i<=itimes; i++ )
90 {
91 if( 0 == i % 10 )
92 {
93 xchange = xchange * 0.1 ; ychange = ychange * 0.1 ;
94 }
95 bestdir = -1 ;//初始化最優方向
96 for( int d=0; d<4; d++ )//向4個方向擴展
97 {
98 double tempx = ansx + xchange * xdir[d] ;
99 double tempy = ansy + ychange * ydir[d] ;
100
101 double curdist = comdist( tempx, tempy ) ;
102 if( curdist < bestdist ) { bestdist = curdist ; bestdir = d ; }
103 }
104 if( bestdir != -1 )
105 {
106 ansx += xchange * xdir[bestdir] ; ansy += ychange * ydir[bestdir] ;
107 }
108 bestdist = comdist( ansx, ansy ) ;
109 }
110 }
111
112 void output()
113 {
114 printf( "%0.1lf %0.1lf %0.1lf\n", ansx, ansy, bestdist ) ;
115 }
116
117 int main()
118 {
119 freopen( "fence3.in", "r", stdin ) ;
120 freopen( "fence3.out","w",stdout ) ;
121
122 while( scanf( "%d", &inn ) != EOF )
123 {
124 input() ;
125
126 process() ;
127
128 output() ;
129 }
130
131 return 0 ;
132 }
|