USACO Electric Fences

题目的意思是求出到所有线段距离之和最小的点的坐标（精确到0.1）并输出这个点到各个线段的距离和。

因为坐标的范围并不大，精度要求也不高，因此，可以把坐标放大10倍，枚举所有整数的点，取距离和最小的点即可。下图就是样例输入经过这样操作的结果：

 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0
 4.9 4.9 4.9 4.9 4.9 4.9 4.9 4.9 4.9 4.9 4.9 4.9 4.9 4.9 4.9 4.9 4.9 4.9 4.9 4.9
 4.8 4.8 4.8 4.8 4.8 4.8 4.8 4.8 4.8 4.8 4.8 4.8 4.8 4.8 4.8 4.8 4.8 4.8 4.8 4.8
 4.7 4.7 4.7 4.7 4.7 4.7 4.7 4.7 4.7 4.7 4.7 4.7 4.7 4.7 4.7 4.7 4.7 4.7 4.7 4.7
 4.6 4.6 4.6 4.6 4.6 4.6 4.6 4.6 4.6 4.6 4.6 4.6 4.6 4.6 4.6 4.6 4.6 4.6 4.6 4.6
 4.5 4.5 4.5 4.5 4.5 4.5 4.5 4.5 4.5 4.5 4.5 4.5 4.5 4.5 4.5 4.5 4.5 4.5 4.5 4.5
 4.4 4.4 4.4 4.4 4.4 4.4 4.4 4.4 4.4 4.4 4.4 4.4 4.4 4.4 4.4 4.4 4.4 4.4 4.4 4.4
 4.3 4.3 4.3 4.3 4.3 4.3 4.3 4.3 4.3 4.3 4.3 4.3 4.3 4.3 4.3 4.3 4.3 4.3 4.3 4.3
 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.2
 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.1
 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.0
 4.0 3.9 3.9 3.9 3.9 3.9 3.9 3.9 3.9 3.9 3.9 3.9 3.9 3.9 3.9 3.9 3.9 3.9 3.9 3.9
 4.0 3.9 3.9 3.9 3.9 3.9 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.9 3.9 3.9 3.9 3.9
 4.0 3.9 3.9 3.9 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.9 3.9 3.9
 4.0 4.0 3.9 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.9 4.0
 4.1 4.0 3.9 3.9 3.8 3.8 3.8 3.8 3.7 3.7 3.7 3.7 3.7 3.8 3.8 3.8 3.8 3.9 3.9 4.0
 4.1 4.0 3.9 3.9 3.8 3.8 3.8 3.8 3.7 3.7 3.7 3.7 3.7 3.8 3.8 3.8 3.8 3.9 3.9 4.0
 4.1 4.0 4.0 3.9 3.9 3.8 3.8 3.8 3.8 3.7 3.7 3.7 3.8 3.8 3.8 3.8 3.9 3.9 4.0 4.0
 4.2 4.1 4.0 3.9 3.9 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.9 3.9 4.0 4.1
 4.2 4.1 4.0 4.0 3.9 3.9 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.8 3.9 3.9 4.0 4.0 4.1
 4.2 4.2 4.1 4.0 4.0 3.9 3.9 3.9 3.8 3.8 3.8 3.8 3.8 3.9 3.9 3.9 4.0 4.0 4.1 4.2
 4.3 4.2 4.1 4.1 4.0 4.0 3.9 3.9 3.9 3.9 3.9 3.9 3.9 3.9 3.9 4.0 4.0 4.1 4.1 4.2
 4.3 4.3 4.2 4.1 4.1 4.0 4.0 4.0 3.9 3.9 3.9 3.9 3.9 4.0 4.0 4.0 4.1 4.1 4.2 4.3
 4.4 4.3 4.2 4.2 4.1 4.1 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.0 4.1 4.1 4.2 4.2 4.3
 4.4 4.4 4.3 4.2 4.2 4.1 4.1 4.1 4.1 4.0 4.0 4.0 4.1 4.1 4.1 4.1 4.2 4.2 4.3 4.4
 4.5 4.4 4.4 4.3 4.2 4.2 4.2 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.2 4.2 4.2 4.3 4.4 4.4
 4.6 4.5 4.4 4.4 4.3 4.3 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.2 4.3 4.3 4.4 4.4 4.5
 4.6 4.6 4.5 4.4 4.4 4.3 4.3 4.3 4.3 4.2 4.2 4.2 4.3 4.3 4.3 4.3 4.4 4.4 4.5 4.6
 4.7 4.6 4.6 4.5 4.5 4.4 4.4 4.4 4.3 4.3 4.3 4.3 4.3 4.4 4.4 4.4 4.5 4.5 4.6 4.6
 4.8 4.7 4.6 4.6 4.5 4.5 4.5 4.4 4.4 4.4 4.4 4.4 4.4 4.4 4.5 4.5 4.5 4.6 4.6 4.7

可以看出，如果f(x,y)表示以(x,y)为供电点到各个篱笆距离之和，那么这个函数会在某个点C取得最小值，并且随着与C距离的增加，f(x,y)的值也在增大。

因此，就有了下面的算法：
任意选取一个点P(x,y)，计算f(x,y)；
然后，把P向周围任意移动1～10个单位长度，获得P'(x',y')，求出f(x',y')。
如果f(x',y')
重复以上步骤大约100次，就可以找到大概的最优位置。

接着，重复上面的步骤100次，不过把P点的移动单位改成0.1。
最后，输出P点的坐标和f(x,y)就可以了。

其实，上面叙述的算法有一个特定的名字——爬山算法（维基百科），是一种在很大的搜索范围内求最优值的算法。不过呢，爬山算法有一个缺陷：可能求得局部最优值，因为爬山算法只会接受比当前解更优的解。

为了弥补这个缺陷，“模拟退火”（维基百科）腾空出世，他与爬山算法的区别就是模拟退火可以随机地接受比当前状况更糟糕的状况，所以有跳出局部最优的可能性。这篇文章对模拟退火有一个通俗的介绍。

这道题的代码如下：

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <math.h>
004 #include <time.h>
005
006 typedef struct POINT
007 {
008     double x,y;
009 }POINT;
010
011 int N;
012 POINT c;
013 POINT wire[150][2];
014 double maxx,maxy,minx,miny;
015
016 double getmin(double a,double b)
017 {
018     if(a < b)    return a;
019     return b;
020 }
021
022 double getmax(double a,double b)
023 {
024     if(a > b)    return a;
025     return b;
026 }
027
028 void init()
029 {
030     int i;
031     double x1,x2,y1,y2;
032     maxx = maxy = 0;
033     minx = miny = 10000;
034     scanf("%d\n",&N);
035     for(i = 0;i < N;i ++)
036     {
037         scanf("%lf %lf %lf %lf\n",&x1,&y1,&x2,&y2);
038         maxx = getmax(maxx,getmax(x1,x2));
039         maxy = getmax(maxy,getmax(y1,y2));
040         minx = getmin(minx,getmin(x1,x2));
041         miny = getmin(miny,getmin(y1,y2));
042         //let [0] be smaller than [1]
043         if(x1 == x2)
044         {
045             wire[i][0].x = wire[i][1].x = x1;
046             if(y1 <= y2)
047             {
048                 wire[i][0].y = y1;
049                 wire[i][1].y = y2;
050             }
051             else
052             {
053                 wire[i][0].y = y2;
054                 wire[i][1].y = y1;
055             }
056         }
057         else if(y1 == y2)
058         {
059             wire[i][0].y = wire[i][1].y = y1;
060             if(x1 <= x2)
061             {
062                 wire[i][0].x = x1;
063                 wire[i][1].x = x2;
064             }
065             else
066             {
067                 wire[i][0].x = x2;
068                 wire[i][1].x = x1;
069             }
070         }
071     }
072     c.x = (maxx + minx) / 2.0;
073     c.y = (maxy + miny) / 2.0;
074 }
075
076 double pdist(POINT a,POINT b)   //dist between two points
077 {
078     return sqrt(pow(a.x - b.x,2) + pow(a.y - b.y,2));
079 }
080
081 double calc_dist(POINT p,POINT a,POINT b)   //dist from p to segment ab
082 {
083     if(a.x == b.x)  //ab parallels to y axis
084     {
085         if(p.y <= b.y && p.y >= a.y)   //p projects to the line
086             return fabs(a.x - p.x);
087         if(p.y < a.y)
088             return pdist(p,a);
089         if(p.y > b.y)
090             return pdist(p,b);
091     }
092     else if(a.y == b.y)  //parallel to x axis
093     {
094         if(p.x <= b.x && p.x >= a.x)   //p projects to the line
095             return fabs(a.y - p.y);
096         if(p.x < a.x)
097             return pdist(p,a);
098         if(p.x > b.x)
099             return pdist(p,b);
100     }
101     return 0;
102 }
103
104 double total_dist(POINT center)
105 {
106     int i;
107     double tot = 0;
108     for(i = 0;i < N;i ++)
109         tot += calc_dist(center,wire[i][0],wire[i][1]);
110     return tot;
111 }
112
113 void solve_1()
114 {
115     POINT p;
116     double dist;
117     double newdist,x,y;
118     int i,j,k;
119     dist = total_dist(c);
120     for(i = 0;i < 1000;i ++)
121     {
122         x = rand() % 10;
123         y = rand() % 10;
124         for(j = -1;j <= 1;j += 2)
125             for(k = -1;k <= 1;k += 2)
126             {
127                 p.x = c.x + x * j;
128                 p.y = c.y + y * k;
129                 newdist = total_dist(p);
130                 if(newdist < dist)
131                 {
132                     c = p;
133                     dist = newdist;
134                 }
135             }
136     }
137 }
138
139 void solve_2()
140 {
141     POINT p;
142     double dist;
143     double newdist,x,y;
144     int i;
145     dist = total_dist(c);
146     for(i = 0;i < 100;i ++)
147     {
148         for(x = -0.1;x <= 0.1;x += 0.1)
149         {
150             for(y = -0.1;y <= 0.1;y += 0.1)
151             {
152                 if(x == 0 && y == 0)    continue;
153                 p.x = c.x + x;
154                 p.y = c.y + y;
155                 newdist = total_dist(p);
156                 if(newdist < dist)
157                 {
158                     c = p;
159                     dist = newdist;
160                 }
161             }
162         }
163     }
164 }
165
166 int main()
167 {
168     freopen("fence3.in","r",stdin);
169     freopen("fence3.out","w",stdout);
170     init();
171     srand(time(NULL));
172     solve_1();
173     solve_2();
174     printf("%.1lf %.1lf %.1lf\n",c.x,c.y,total_dist(c));
175     return 0;
176 }