poj 2420 A Star not a Tree？馬点がかかる

    ：http://acm.pku.edu.cn/JudgeOnline/problem?id=2420

    ：                        ，    。

//0ms

#include<cstdio>
#include<iostream>
#include<math.h>
#define eps 1e-8
using namespace std;

const int maxn=120;
struct point{double x,y;}points[maxn],st;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int n;

double dis(point p1,point p2)
{
	return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double alldis(point tmp)
{
	double sum=0;
	int i;
	for(i=0;i<n;i++)
	{
		sum+=dis(tmp,points[i]);
	}
	return sum;
}

double slove(double step)
{
	double minn=1000000000; while(step>0.2)
	{
		bool isok=true;
		while(isok)
		{
			int i;
			isok=false;
			for(i=0;i<4;i++)
			{
				point temp=st;
				temp.x+=dir[i][0]*step;
				temp.y+=dir[i][1]*step;
				double dis=alldis(temp);
				if(minn>dis)
				{
					isok=true;
					minn=dis;
					st=temp;
				}
				
			}
		}
		step/=2.0;
	}
	return minn;
}

int main()
{
	while(~scanf("%d",&n))
	{
		int i;
		for(i=0;i<n;i++)
			scanf("%lf%lf",&points[i].x,&points[i].y);
		st=points[0];
		printf("%d
",(int)(slove(1000)+0.5));
	}
	return 0;
}