2015
04-14

# Groundhog Build Home

Groundhogs are good at digging holes, their home is a hole, usually a group of groundhogs will find a more suitable area for their activities and build their home at this area .xiaomi has grown up, can no longer live with its parents.so it needs to build its own home.xiaomi like to visit other family so much, at each visit it always start from the point of his own home.Xiaomi will visit all of the groundhogs’ home in this area(it will chose the linear distance between two homes).To save energy,xiaomi would like you to help it find where its home built,so that the longest distance between xiaomi’s home and the other groundhog’s home is minimum.

The input consists of many test cases，ending of eof.Each test case begins with a line containing three integers X, Y, N separated by space.The numbers satisfy conditions: 1 <= X,Y <=10000, 1 <= N<= 1000. Groundhogs acivity at a rectangular area ,and X, Y is the two side of this rectangle, The number N stands for the number of holes.Then exactly N lines follow, each containing two integer numbers xi and yi (0 <= xi <= X, 0 <= yi <= Y) indicating the coordinates of one home.

The input consists of many test cases，ending of eof.Each test case begins with a line containing three integers X, Y, N separated by space.The numbers satisfy conditions: 1 <= X,Y <=10000, 1 <= N<= 1000. Groundhogs acivity at a rectangular area ,and X, Y is the two side of this rectangle, The number N stands for the number of holes.Then exactly N lines follow, each containing two integer numbers xi and yi (0 <= xi <= X, 0 <= yi <= Y) indicating the coordinates of one home.

1000 50 1
10 10
1000 50 4
0 0
1 0
0 1
1 1

(10.0,10.0).
0.0
(0.5,0.5).
0.7

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;

const double eps=1e-8;
const int n_max=1005;
double X,Y,R;
int n;
struct point
{
double x,y;
point(){}
point(double tx,double ty)
{
x=tx,y=ty;
}
}p[n_max],central;

double dist(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

//求外接圆圆心
point circumcenter(point a,point b,point c)
{
double a1=b.x-a.x, b1=b.y-a.y, c1=(a1*a1+b1*b1)/2;
double a2=c.x-a.x, b2=c.y-a.y, c2=(a2*a2+b2*b2)/2;
double d=a1*b2-a2*b1;
return point(a.x + (c1*b2-c2*b1)/d , a.y+(a1*c2-a2*c1)/d);
}

//求最小覆盖圆
void min_cover_circle()
{
random_shuffle(p,p+n);
central=p[0];
R=0;
int i,j,k;
for(i=1;i<n;i++)
{
if(dist(central,p[i])+eps>R)
{
central=p[i];
R=0;
for(j=0;j<i;j++)
{
if(dist(central,p[j])+eps>R)
{
central.x=(p[i].x+p[j].x)/2;
central.y=(p[i].y+p[j].y)/2;
R=dist(central,p[j]);
for(k=0;k<j;k++)
{
if(dist(central,p[k])+eps>R)
{
central=circumcenter(p[i],p[j],p[k]);
R=dist(central,p[k]);
}
}
}
}
}
}
}

int main()
{
while(~scanf("%lf%lf%d",&X,&Y,&n))
{
int i;
for(i=0;i<n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
}
min_cover_circle();
printf("(%.1lf,%.1lf).\n%.1lf\n",central.x,central.y,R);
}
return 0;
}


1. 可以参考算法导论中的时间戳。就是结束访问时间，最后结束的顶点肯定是入度为0的顶点，因为DFS要回溯

2. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。