首页 > ACM题库 > HDU-杭电 > HDU 3932-Groundhog Build Home[解题报告]HOJ
2015
04-14

HDU 3932-Groundhog Build Home[解题报告]HOJ

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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/makingmaker/article/details/8108880


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

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

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  4. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.