比赛 20111102 评测结果 AAAAAAAAAA
题目名称 麻烦的干草打包机 最终得分 100
用户昵称 Makazeu 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-11-02 20:12:34
显示代码纯文本
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;

class ROLLER
{
public:
	int x;
	int y;
	int r;
	double s;
}Roller[1051];
int N;
int X,Y;
int ENum;
int SNum;

long long squre(int a)
{
	long long tmp=a*a;
	return tmp;
}

void init()
{
	scanf("%d %d %d\n",&N,&X,&Y);
	for (int i=1;i<=N;i++)
	{
		scanf("%d %d %d\n",&Roller[i].x,&Roller[i].y,&Roller[i].r);
	
		if(Roller[i].x==0 && Roller[i].y==0)
			SNum=i;
		
		if(Roller[i].x==X && Roller[i].y==Y)
			ENum=i;
	}
	Roller[SNum].s=10000;
}


class QUEUE
{
public:
	double S;//當前輪子轉速
	int C;//當前輪子的編號
	bool Rol[1051];
	QUEUE()
	{
		for (int i=1;i<=1050;i++)
			Rol[i]=true;
	}
}Q[1200];


double GetSpeed(double ss,int rd,int rx)
{
	double rrd=(double)(rd);
	double rrx=(double)(rx);
	double res=-ss*rrd/rrx;
	return res;
}

double absd(double aa)
{
	if(aa>=0)
		return aa;
	else
		return -aa;
}
	

int bfs()
{
	int Big=1;
	int Small=0;
	Q[0].Rol[SNum]=false;
	Q[0].C=SNum;
	Q[0].S=10000;
	
	int Tn,Tx,Ty,Tr;
	double Ts;
	int Nx,Ny,Nr;
	long long ta,tb,tc;
	while(Small<=Big)
	{
		Tn=Q[Small].C;
		Tx=Roller[Tn].x;
		Ty=Roller[Tn].y;
		Tr=Roller[Tn].r;
		Ts=Q[Small].S;
		
		for (int i=1;i<=N;i++)
		{
			if(i==Tn)
				continue;
			
			if(!Q[Small].Rol[i])
				continue;
			
			Nx=Roller[i].x;
			Ny=Roller[i].y;
			Nr=Roller[i].r;
			
			ta=squre(Nx-Tx);
			tb=squre(Ny-Ty);
			tc=squre(Nr+Tr);
			
			if( ta+tb!=tc )
				continue;
			
			for (int k=1;k<=N;k++)
				Q[Big].Rol[k]=Q[Small].Rol[k];
			Q[Big].C=i;
			Q[Big].S=GetSpeed(Ts,Tr,Nr);
			Q[Big].Rol[i]=false;
			Roller[i].s=Q[Big].S;
			if(i==ENum)
				return Big;
			
			Big++;
		}
		
		Small++;
	}
	return Big;
}

int main()
{
	freopen("baler.in","r",stdin);
	freopen("baler.out","w",stdout);
	init();
	int EQ=bfs();
	double Tot=0;
	for (int i=1;i<=N;i++)
	{
		if(!Q[EQ].Rol[i])
			Tot=Tot+absd(Roller[i].s);
	}
	cout<<(int)(Tot)<<endl;
	return 0;
}