比赛 |
20111102 |
评测结果 |
AAAAAAAAAA |
题目名称 |
麻烦的干草打包机 |
最终得分 |
100 |
用户昵称 |
Czb。 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-11-03 09:29:48 |
显示代码纯文本
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
FILE *fi=fopen("baler.in","r");
FILE *fo=fopen("baler.out","w");
struct aaa
{
double x,y,r,v;
}a[1100];
int n,s,v[1100][1100],t[1100];
bool b[1100];
double x,y,ans;
void dfs(int k)
{
int i;
if(a[k].x==x&&a[k].y==y)
{
fprintf(fo,"%.0lf\n",ans);
fclose(fi);
fclose(fo);
exit(0);
}
for(i=1;i<=t[k];i++)
{
if(!b[v[k][i]])
{
a[v[k][i]].v=a[k].v*a[k].r/a[v[k][i]].r;
ans+=a[v[k][i]].v;
b[v[k][i]]=true;
dfs(v[k][i]);
b[v[k][i]]=false;
ans-=a[v[k][i]].v;
}
}
}
int main()
{
int i,j;
fscanf(fi,"%d%lf%lf",&n,&x,&y);
for(i=1;i<=n;i++)
{
fscanf(fi,"%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r);
if(a[i].x==0&&a[i].y==0)
s=i;
}
for(i=1;i<n;i++)
{
for(j=i+1;j<=n;j++)
{
if((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)==(a[i].r+a[j].r)*(a[i].r+a[j].r))
{
t[i]++;
v[i][t[i]]=j;
t[j]++;
v[j][t[j]]=i;
}
}
}
a[s].v=10000;
ans=10000;
b[s]=true;
dfs(s);
return 0;
}