4650484_ac_16ms_260k.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 77 行

#include<iostream>
#include<iomanip>
#include<math.h>
using namespace std;
float dis[205];
float result;
struct point
{
	float x;
	float y;
}p[205];
bool open[205];
int n;
float getdis(point a,point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int pickmin()
{
	float tmin=10000000;
	int re;
	for(int count=1;count<=n;count++)
	{
		if(open[count]==false)
		{
			if(dis[count]<tmin)
			{
				re=count;
				tmin=dis[count];
			}
		}
	}
	return re;
}
void DJ()
{
	memset(open,false,sizeof(open));
	for(int i=1;i<=n;i++)
	{
		dis[i]=10000000.0;
	}
	int opn=0;
	dis[1]=0;
	while(opn<n)
	{
		int temp=pickmin();
		open[temp]=true;
		opn++;
		for(int count=1;count<=n;count++)
		{
			if(count!=temp)
			{
				float t=getdis(p[temp],p[count]);
				float t2=t>dis[temp]?t:dis[temp];
				if(t2<dis[count]) dis[count]=t2;
			}
		}
	}
	result=dis[2];
}
int main()
{
	int testnumber=0;
	while(cin>>n)
	{
		testnumber++;
		if(n==0) return 0;
		for(int count=1;count<=n;count++)
		{
			cin>>p[count].x>>p[count].y;
		}
		DJ();
		printf("Scenario #%d\n",testnumber);
		printf("Frog Distance = %.3f\n\n", result);
	}
	return 0;
}