比赛 20111102 评测结果 AAAAAAAAAA
题目名称 麻烦的干草打包机 最终得分 100
用户昵称 Citron酱 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-11-02 19:38:48
显示代码纯文本
#include <fstream>
#include <cmath>

#define I_F "baler.in"
#define O_F "baler.out"

const int MAXn=1050;
const int C=10000;
const double P=0.01;

struct cl
{
	int x,y,r;
	double c;
}s[MAXn];
int n,a,b;
double ans=C;

void Input();
inline double Sqr(const double);
inline bool Pd(const int, const int);
inline double GetC(const int, const int);
bool Dfs(const int);
void Output();

int main()
{
	Input();
	Dfs(a);
	Output();
	return 0;
}

void Input()
{
	int x,y;
	std::ifstream fin(I_F);
	fin>>n>>x>>y;
	for (int i=0; i<n; i++)
	{
		fin>>s[i].x>>s[i].y>>s[i].r;
		s[i].c=0;
		if (s[i].x==0 && s[i].y==0)
			a=i,
			s[i].c=C;
		else if (s[i].x==x && s[i].y==y)
			b=i;
	}
	fin.close();
}

inline double Sqr(const double x)
{
	return x*x;
}

inline bool Pd(const int x, const int y)
{
	return (sqrt(Sqr(s[x].x-s[y].x)+Sqr(s[x].y-s[y].y))-s[x].r-s[y].r<=P);
}

inline double GetC(const int x, const int y)
{
	return (s[x].c*s[x].r/s[y].r);
}

bool Dfs(const int x)
{
	if (x==b)
		return true;
	for (int i=0; i<n; i++)
		if (s[i].c==0 && Pd(x,i))
		{
			s[i].c=GetC(x,i);
			ans+=s[i].c;
			if (Dfs(i))
				return true;
			ans-=s[i].c;
		}
	return false;
}

void Output()
{
	std::ofstream fout(O_F);
	fout<<(int)ans<<std::endl;
	fout.close();
}