Question

浙大acm题高手进 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3208

#include<stdio.h>
#include<math.h>
struct len
{
double d;
int x;
int y;
double h;

}num[200],t;

int main()
{
int fun();
int i,j,n,T,k;
scanf("%d",&T);
for(k=0;k<T;k++)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d %d",&num[i].x,&num[i].y);
num[i].d=sqrt(num[i].x*num[i].x+num[i].y*num[i].y);
}
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(num[i].d>num[j].d) {t=num[i];num[i]=num[j];num[j]=t;}
}
}
i=0;
if((double)fun(i,n)!=0)
printf("%lf\n",(double)fun(i,n));
else
break;
}
return 0;
}

int fun(int i,int n)
{
int time=0,j; double y;
num[i].h=1000000;
for(i=0;i<n;i++)
{
y=sqrt((num[i].x-num[i+1].x)*(num[i].x-num[i+1].x)+(num[i].y-num[i+1].y)*(num[i].y-num[i+1].y));
if(num[i].h>y) num[i].h=y;
}
if(((num[i].h)/2)>num[i].d) {time=((int)num[i].d)+1; return time;}
else
{
if(num[i].x*num[i+1].x<0||num[i].x*num[i+1].x==0) {printf("-1.0\n");return 0;}
else
{
for(j=2;j<n;j++)
{
if(num[i].x*num[j].x<0)
{
return fun(j,n);
}
}
}
分数不是问题
}

}
这个程序哪错啦
提交结果是wrong answer

Answer 1

看你的代码看的蛋疼。 先说说你的思路吧。

我觉得应该仿照图的常用算法，也就是贪心算法。拦汪橡
核心数据结构为
struct Distance
{
double val; // distance value
int adj_tree; // index of the adjacent tree to which we calculate the distance
};
struct Tree
{
double x, y; // coordinates
Distance* dist_array; // distance to each tree
double dist_to_observer; // distance to the observer
bool grown; // the tree has grown up
};
思路为：
1. 对每棵树保留其到其他所有树的距离并排序（这样dist_array[0]肯定是自己,无视之）
2. 选出有全场最小距离的树(要么dist_array[1]全场最小，要么dist_to_observer全场最小)
3. 计算出此树的最大半径：
a. radius = dist_to_observer
b.遍历dist_array，若adj_tree已经grow则radius取现值和val的较小值，若未grow则取现值和val/2的较小值
c.如果这颗树的radius史上最大则保存
4. 令其长大，set grown=true。
5. 对任一其它树的dist_array中和当前树相关的距离减去简旁radius
6. 遍历当前树的dist_array，找到第一个尚未grow的树，设定为当前树，跳到3，若找不到则结束

在步骤3或者4中求出过observer到当前树形成的园的两根切线形成的角度区间，
保存下来，不断并集，最后如果能够撑满(0, 2*PI),则最大radius为所求，否则-1。

我不是什么acm高手，所以以上算法效率也不是很高，如果你有更好陵敏的算法也请提出来一起来研究研究。