记录编号	79250	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 麻烦的干草打包机	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2013-11-05 11:22:49	内存使用	0.36 MiB

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<map>
#include<set>
#include<deque>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;
const int SIZEN=1050+9;
int S,T;
int n;
double x[SIZEN]={0},y[SIZEN]={0},r[SIZEN]={0};
double rev[SIZEN]={0};
vector<int> c[SIZEN];
bool useful[SIZEN]={0};
bool DFS(int x,int father){
	if(x==T){
		useful[x]=true;
		return true;
	}
	int i;
	int u;
	double nextrev;
	bool flag=false;
	for(i=0;i<c[x].size();i++){
		u=c[x][i];
		if(u==father) continue;
		rev[u]=-rev[x]*r[x]/r[u];
		if(DFS(u,x)) flag=true;
	}
	if(flag) useful[x]=true;
	return flag;
}
bool is_adj(int a,int b){
	double dist=(x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
	return dist==(r[a]+r[b])*(r[a]+r[b]);
}
void makegraph(void){
	int i,j;
	for(i=1;i<=n;i++){
		for(j=i+1;j<=n;j++){
			if(is_adj(i,j)){
				c[i].push_back(j);
				c[j].push_back(i);
			}
		}
	}
}
void init(void){
	double xt,yt;
	scanf("%d%lf%lf",&n,&xt,&yt);
	int i;
	for(i=1;i<=n;i++){
		scanf("%lf%lf%lf",&x[i],&y[i],&r[i]);
		if(x[i]==0&&y[i]==0) S=i;
		if(x[i]==xt&&y[i]==yt) T=i;
	}
	rev[S]=10000;
}
void stat(void){
	double sum=0;
	int i;
	for(i=1;i<=n;i++){
		if(useful[i]) sum+=fabs(rev[i]);
	}
	printf("%.0lf\n",sum);
}
int main(){
	freopen("baler.in","r",stdin);
	freopen("baler.out","w",stdout);
	init();
	makegraph();
	DFS(S,-1);
	stat();
	return 0;
}