简单模拟,对于第i个冰壶,如果k∈[0,i-1]范围的冰壶k阻碍了冰壶,即:
|xi−xk|<2r
则假设冰壶i能走到冰壶k与之碰撞i。计算此时冰壶y,我们对每一个情况都做判断,找出最大的y即可。
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct ps{
int x;double y;
}p[1005];
int ti,n,r;
double ty;
int main(){
scanf("%d%d",&n,&r);
for(int i=0;i<n;i++){
scanf("%d",&p[i].x);
}
for(int i=0;i<n;i++){
p[i].y=0;
for(int j=0;j<i;j++){
if(abs(p[j].x-p[i].x)<=r*2){
ty=p[ti=j].y;
p[i].y=max(p[i].y,ty+sqrt(4*r*r-abs(p[ti].x-p[i].x)*abs(p[ti].x-p[i].x)));
}
}
if(p[i].y==0)p[i].y=r;
}
for(int i=0;i<n;i++)printf("%.8lf ",p[i].y);
}