Farmer John has decided to construct electric fences. He hasfenced his fields into a number of bizarre shapes and now must findthe optimal place to locate the electrical supply to each of thefences.

A single wire must run from some point on each and every fenceto the source of electricity. Wires can run through other fencesor across other wires. Wires can run at any angle. Wires can runfrom any point on a fence (i.e., the ends or anywhere in between)to the electrical supply.

Given the locations of all F (1 <= F <= 150) fences (fencesare always parallel to a grid axis and run from one integer gridpointto another, 0 <= X,Y <= 100), your program must calculateboth the total length of wire required to connect every fence tothe central source of electricity and also the optimal location forthe electrical source.

The optimal location for the electrical source might be anywherein Farmer John‘s field, not necessarily on a grid point.

PROGRAM NAME: fence3

INPUT FORMAT

The first line contains F, the number of fences.
F subsequentlines each contain two X,Y pairs each of which denotes the endpointsof a fence.

SAMPLE INPUT (file fence3.in)

30 0 0 12 0 2 10 3 2 3

OUTPUT FORMAT

On a single line, print three space-separated floating point numbers, each with a single decimal place. Presume that your computer‘s output library will round the number correctly.

The three numbers are:

• the X value of the optimal location for the electricity,
• the Y value for the optimal location for the electricity, and
• the total (minimum) length of the wire required.

SAMPLE OUTPUT (file fence3.out)

1.0 1.6 3.7

题意：给出N条平行于坐标轴的线段，要求一点，使得该点到所有线段之和最小。

由于精度要求很低，只要保留一位小数，所以可以随便乱搞，我就是在整数范围内先暴力找到一个满足题意的点，然后在x±1，y±1范围内暴力找到小数点后一位，最坏的情况需要暴力100*100*150，也是完全可以承受的。

暴力小数位的时候要注意精度问题，另外三分搜索也可以做。

Executing...
   Test 1: TEST OK [0.014 secs, 3380 KB]
   Test 2: TEST OK [0.016 secs, 3380 KB]
   Test 3: TEST OK [0.049 secs, 3380 KB]
   Test 4: TEST OK [0.024 secs, 3380 KB]
   Test 5: TEST OK [0.070 secs, 3380 KB]
   Test 6: TEST OK [0.046 secs, 3380 KB]
   Test 7: TEST OK [0.043 secs, 3380 KB]
   Test 8: TEST OK [0.051 secs, 3380 KB]
   Test 9: TEST OK [0.057 secs, 3380 KB]
   Test 10: TEST OK [0.046 secs, 3380 KB]
   Test 11: TEST OK [0.049 secs, 3380 KB]
   Test 12: TEST OK [0.076 secs, 3380 KB]

All tests OK.

  1 /*  2 LANG:C++  3 TASK:fence3  4 */  5   6 #include <iostream>  7 #include <cmath>  8 #include <stdio.h>  9 using namespace std; 10 #define X first 11 #define Y second 12  13 typedef pair<double,double> Point; 14 int n; 15  16 struct Fence 17 { 18     Point p1; 19     Point p2; 20 }fences[160]; 21  22 double dist_point(Point p1,Point p2) 23 { 24     return sqrt((double)(p1.X-p2.X)*(p1.X-p2.X)+(p1.Y-p2.Y)*(p1.Y-p2.Y)); 25 } 26  27 bool isIn(Fence f,Point p) 28 { 29     if(f.p1.X==f.p2.X) // 垂直方向 30         return f.p1.Y<=p.Y && p.Y<=f.p2.Y; 31     if(f.p1.Y==f.p2.Y) // 水平方向 32         return f.p1.X<=p.X && p.X<=f.p2.X; 33 } 34  35 // 计算p点到各篱笆的距离 36 double dist(Point p) 37 { 38     double ans=0; 39     for(int i=0;i<n;i++) 40     { 41         if(isIn(fences[i],p)) 42         { 43             if(fences[i].p1.X==fences[i].p2.X) // 垂直方向 44             { 45                 ans+=fabs((double)p.X-fences[i].p1.X); 46             } 47             else 48             { 49                 ans+=fabs((double)p.Y-fences[i].p1.Y); 50             } 51         } 52         else 53         { 54             ans+=min(dist_point(p,fences[i].p1),dist_point(p,fences[i].p2)); 55         } 56     } 57     return ans; 58 } 59  60  61 int main() 62 { 63     freopen("fence3.in","r",stdin); 64     freopen("fence3.out","w",stdout); 65  66     cin>>n; 67     for(int i=0;i<n;i++) 68     { 69         scanf("%lf %lf %lf %lf",&fences[i].p1.X,&fences[i].p1.Y,&fences[i].p2.X,&fences[i].p2.Y); 70     } 71  72     Point p; 73     double d=1e100; 74  75     for(int i=0;i<=100;i++) 76         for(int j=0;j<=100;j++) 77         { 78             if(d>dist(Point((double)i,(double)j))) 79             { 80                 p=Point((double)i,(double)j); 81                 d=dist(Point((double)i,(double)j)); 82             } 83         } 84  85  86     Point p2=p; 87     p2.X-=1; 88     p2.Y-=1; 89     Point ans; 90     for(;p2.X<=p.X+1;p2.X+=0.1) 91         for(p2.Y=p.Y-1;p2.Y<=p.Y+1;p2.Y+=0.1) 92         { 93             if(d>=dist(p2)-1e-12) 94             { 95                 ans=p2; 96                 d=dist(p2); 97             } 98         } 99 100     printf("%.1f %.1f %.1f\n",ans.X,ans.Y,d);101 102     return 0;103 }

USACO6.4-Electric Fences:计算几何