USACO6.4-Electric Fences:计算几何

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Electric Fences
Kolstad & Schrijvers

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

A single wire must run from some point on each and every fence
to the source of electricity. Wires can run through other fences
or across other wires. Wires can run at any angle. Wires can run
from 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 (fences
are always parallel to a grid axis and run from one integer gridpoint
to another, 0 <= X,Y <= 100), your program must calculate
both the total length of wire required to connect every fence to
the central source of electricity and also the optimal location for
the electrical source.

The optimal location for the electrical source might be anywhere
in 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 subsequent
lines each contain two X,Y pairs each of which denotes the endpoints
of a fence.

SAMPLE INPUT (file fence3.in)

3
0 0 0 1
2 0 2 1
0 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.

/*
LANG:C++
TASK:fence3
*/ #include <iostream>
#include <cmath>
#include <stdio.h>
using namespace std;
#define X first
#define Y second typedef pair<double,double> Point;
int n; struct Fence
{
Point p1;
Point p2;
}fences[]; double dist_point(Point p1,Point p2)
{
return sqrt((double)(p1.X-p2.X)*(p1.X-p2.X)+(p1.Y-p2.Y)*(p1.Y-p2.Y));
} bool isIn(Fence f,Point p)
{
if(f.p1.X==f.p2.X) // 垂直方向
return f.p1.Y<=p.Y && p.Y<=f.p2.Y;
if(f.p1.Y==f.p2.Y) // 水平方向
return f.p1.X<=p.X && p.X<=f.p2.X;
} // 计算p点到各篱笆的距离
double dist(Point p)
{
double ans=;
for(int i=;i<n;i++)
{
if(isIn(fences[i],p))
{
if(fences[i].p1.X==fences[i].p2.X) // 垂直方向
{
ans+=fabs((double)p.X-fences[i].p1.X);
}
else
{
ans+=fabs((double)p.Y-fences[i].p1.Y);
}
}
else
{
ans+=min(dist_point(p,fences[i].p1),dist_point(p,fences[i].p2));
}
}
return ans;
} int main()
{
freopen("fence3.in","r",stdin);
freopen("fence3.out","w",stdout); cin>>n;
for(int i=;i<n;i++)
{
scanf("%lf %lf %lf %lf",&fences[i].p1.X,&fences[i].p1.Y,&fences[i].p2.X,&fences[i].p2.Y);
} Point p;
double d=1e100; for(int i=;i<=;i++)
for(int j=;j<=;j++)
{
if(d>dist(Point((double)i,(double)j)))
{
p=Point((double)i,(double)j);
d=dist(Point((double)i,(double)j));
}
} Point p2=p;
p2.X-=;
p2.Y-=;
Point ans;
for(;p2.X<=p.X+;p2.X+=0.1)
for(p2.Y=p.Y-;p2.Y<=p.Y+;p2.Y+=0.1)
{
if(d>=dist(p2)-1e-)
{
ans=p2;
d=dist(p2);
}
} printf("%.1f %.1f %.1f\n",ans.X,ans.Y,d); return ;
}