首页 > ACM题库 > HDU-杭电 > HDU 3007-Buried memory-计算几何-[解题报告]HOJ
2014
02-27

HDU 3007-Buried memory-计算几何-[解题报告]HOJ

Buried memory

问题描述 :

Each person had do something foolish along with his or her growth.But,when he or she did this that time,they could not predict that this thing is a mistake and they will want this thing would rather not happened.
The world king Sconbin is not the exception.One day,Sconbin was sleeping,then swakened by one nightmare.It turned out that his love letters to Dufein were made public in his dream.These foolish letters might ruin his throne.Sconbin decided to destroy the letters by the military exercises’s opportunity.The missile is the best weapon.Considered the execution of the missile,Sconbin chose to use one missile with the minimum destruction.
Sconbin had writen N letters to Dufein, she buried these letters on different places.Sconbin got the places by difficult,he wants to know where is the best place launch the missile,and the smallest radius of the burst area. Let’s help Sconbin to get the award.

输入:

There are many test cases.Each case consists of a positive integer N(N<500,^V^,our great king might be a considerate lover) on a line followed by N lines giving the coordinates of N letters.Each coordinates have two numbers,x coordinate and y coordinate.N=0 is the end of the input file.

输出:

There are many test cases.Each case consists of a positive integer N(N<500,^V^,our great king might be a considerate lover) on a line followed by N lines giving the coordinates of N letters.Each coordinates have two numbers,x coordinate and y coordinate.N=0 is the end of the input file.

样例输入:

3
1.00 1.00
2.00 2.00
3.00 3.00
0

样例输出:

2.00 2.00 1.41

题意:给出平面上的一些点,要求用一个最小的圆,把所有的点包围起来。

最小覆盖圆, 增量法
假设圆O是前i-1个点得最小覆盖圆,加入第i个点,如果在圆内或边上则什么也不做。否,新得到的最小覆盖圆肯定经过第i个点。
然后以第i个点为基础(半径为0),重复以上过程依次加入第j个点,若第j个点在圆外,则最小覆盖圆必经过第j个点。
重复以上步骤(因为最多需要三个点来确定这个最小覆盖圆,所以重复三次)。遍历完所有点之后,所得到的圆就是覆盖所有点得最小圆。

证明可以考虑这么做:
最小圆必定是可以通过不断放大半径,直到所有以任意点为圆心,半径为半径的圆存在交点,此时的半径就是最小圆。所以上述定理可以通过这个思想得到。这个做法复杂度是O(n)的,当加入圆的顺序随机时,因为三点定一圆,所以不在圆内概率是3/i,求出期望可得是O(n)。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm> 
using namespace std;
const double eps=1e-8;
struct Point{
	double x,y; 
}p[505];
double dis(const Point &a,const Point &b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 
} 
Point circumcenter(const Point &a,const Point &b,const Point &c)
{ //返回三角形的外心 
	Point ret; 
	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;
	ret.x=a.x+(c1*b2-c2*b1)/d;
	ret.y=a.y+(a1*c2-a2*c1)/d;
	return ret; 
} 
void min_cover_circle(Point *p,int n,Point &c,double &r){ //c为圆心,r为半径 
	random_shuffle(p,p+n); // 
	c=p[0]; r=0;
	for(int i=1;i<n;i++)
	{
		if(dis(p[i],c)>r+eps)  //第一个点
		{ 
			c=p[i]; r=0;
			for(int j=0;j<i;j++)
				if(dis(p[j],c)>r+eps) //第二个点
				{
					c.x=(p[i].x+p[j].x)/2;
					c.y=(p[i].y+p[j].y)/2;
					r=dis(p[j],c);
					for(int k=0;k<j;k++)
						if(dis(p[k],c)>r+eps) //第三个点
						{//求外接圆圆心,三点必不共线 
							c=circumcenter(p[i],p[j],p[k]); 
							r=dis(p[i],c); 
						} 
				}  
		}    
	} 
} 
int main(){
	int n;
	Point c;
	double r; 
	while(scanf("%d",&n)==1 && n){
		for(int i=0;i<n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		min_cover_circle(p,n,c,r);                    
		printf("%.2lf %.2lf %.2lf\n",c.x,c.y,r);                   
	} 
	return 0;
}

 

参考:http://blog.csdn.net/vsooda/article/details/8543450


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  3. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts

  4. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.