这个题可以转化一下。
dp [ i ] = min ( dp [ i ] , sqrt ( dp [ j ] * dp [ j ] + dis ( i , j ) ) )

i点 ( 0 , ai1 , ai2 )
j点 ( dpj , aj1 , aj2)

就是求 i 点之前距离 i 最近的点。
其中：
k=1时是二维坐标。
k=2时是三维坐标。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=1000100;
const double alpha=0.75;
const int inf=0x3f3f3f3f;
struct Point
{
    double x[3];
}po[maxn];
struct node
{
    double p[3];
    int lc,rc;
    double mi[3],ma[3];
   int si;
}t[maxn];

int root,cnt,sum,now_maxx;
double res[3];
int ans;
int hui[maxn],top;
int nowd;
int dd,*pp;
double dp[maxn];

bool cmp(const Point &a,const Point &b)
{
    return a.x[nowd]<b.x[nowd];
}

bool balance(int q)
{
    return (double)t[t[q].lc].si<=t[q].si*alpha&&(double)t[t[q].rc].si<=t[q].si*alpha;
}

int newnode(int k)
{
    int p=0;
    if(top) p=hui[top--];
    else p=++cnt;
    t[p].si=t[p].lc=t[p].rc=0;
    for(int i=0;i<now_maxx;i++)
        t[p].mi[i]=t[p].ma[i]=t[p].p[i]=po[k].x[i];

    return p;
}

void  pushup(int p)
{
    int lc=t[p].lc,rc=t[p].rc;
    for(int i=0;i<now_maxx;i++)
    {
        if(lc) t[p].mi[i]=min(t[p].mi[i],t[lc].mi[i]),t[p].ma[i]=max(t[p].ma[i],t[lc].ma[i]);
        if(rc) t[p].mi[i]=min(t[p].mi[i],t[rc].mi[i]),t[p].ma[i]=max(t[p].ma[i],t[rc].ma[i]);
    }
    t[p].si=t[lc].si+t[rc].si+1;
}


int build(int l,int r,int d)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    nowd=d;
    nth_element(po+l,po+mid,po+r+1,cmp);
    int p=newnode(mid);
    t[p].lc=build(l,mid-1,(d+1)%now_maxx);
    t[p].rc=build(mid+1,r,(d+1)%now_maxx);
    pushup(p);
    return p;
}

void _insert(int &p,int k,int d)
{
    if(!p)
    {
        pp=NULL;
        p=newnode(k);
        return ;
    }
    if(po[k].x[d]<t[p].p[d])
        _insert(t[p].lc,k,(d+1)%now_maxx);
    else _insert(t[p].rc,k,(d+1)%now_maxx);
    pushup(p);
    if(!balance(p)) pp=&p,dd=d;
}


void dfs(int p)
{
    if(t[p].lc) dfs(t[p].lc);
    ++sum;
    for(int i=0;i<now_maxx;i++)
        po[sum].x[i]=t[p].p[i];
    hui[++top]=p;
    if(t[p].rc) dfs(t[p].rc);
}

void rebuild(void)
{
    sum=0;
    dfs(*pp);
    (*pp)=build(1,sum,dd);
}

void _insert(int k)
{
    _insert(root,k,0);
    if(pp!=NULL) rebuild();
}

inline double dis(int p)
{
    double ans=0;
    for(int i=0;i<now_maxx;i++)
        ans+=(t[p].p[i]-res[i])*(t[p].p[i]-res[i]);
    return ans;
}

inline double di(int p)
{
    int ans=0;
    for(int i=0;i<now_maxx;i++)
        ans+=(max(t[p].mi[i]-res[i],0.0)+max(res[i]-t[p].ma[i],0.0))*(max(t[p].mi[i]-res[i],0.0)+max(res[i]-t[p].ma[i],0.0));
    return ans;
}

void ask(int p)
{
    if(!p) return ;
    if(dis(p)<dis(ans)) ans=p;
    int dl=inf,dr=inf;
    if(t[p].lc) dl=di(t[p].lc);
    if(t[p].rc) dr=di(t[p].rc);
    if(dl<dr)
    {
        if(dl<dis(ans))
            ask(t[p].lc);
        if(dr<dis(ans))
            ask(t[p].rc);
    }
    else
    {
       if(dr<dis(ans))
            ask(t[p].rc);
        if(dl<dis(ans))
            ask(t[p].lc);
    }
}

void do2(int n)
{
    now_maxx=3;
    po[0].x[0]=0,po[0].x[1]=0,po[0].x[2]=0;
    _insert(0);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&res[0],&res[1]);
        res[2]=0,ans=1;
        ask(root);
        dp[i]=sqrt(dis(ans));
        po[i].x[0]=res[0],po[i].x[1]=res[1],po[i].x[2]=dp[i];
        _insert(i);
    }
    for(int i=1;i<=n;i++)
        printf("%.4f\n",dp[i]);
}

void do1(int n)
{
    now_maxx=2;
    po[0].x[0]=0,po[0].x[1]=0;
    _insert(0);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&res[0]);
        res[1]=0,ans=1;
        ask(root);
        dp[i]=sqrt(dis(ans));
        po[i].x[0]=res[0],po[i].x[1]=dp[i];
        _insert(i);
    }
    for(int i=1;i<=n;i++)
        printf("%.4f\n",dp[i]);
}

int main(void)
{
    int n,k;
    scanf("%d%d",&n,&k);
    if(k==1) do1(n);
    else do2(n);
    return 0;
}