prow2012-A3-0021

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

类似凸包的扫描方法，每次把凹的维护成凸的，就是最短距离。

{{{

#include <stdio.h>
#include <math.h>
#include <map>
#include <algorithm>
#include <string.h>
using namespace std;
double X[1000000],Y[1000000];
bool ral(int i,int j,int k){
    return (X[j]-X[i])*(Y[k]-Y[i])>(X[k]-X[i])*(Y[j]-Y[i]);
}
double calc(int i,int j){
    return sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]));
}
int Q[1000000];
int main(){
    int N,i,L,R;
    while(scanf("%d",&N)!=EOF){
        for (i=0;i<N;i++)
            scanf("%lf%lf",&X[i],&Y[i]);
        Q[0] = 0;
        L = 0,R = 1;
        for (i=1;i<N;i++)
        {
            while(L<R-1&&!ral(Q[R-2],i,Q[R-1]))
                R--;
            Q[R++] = i;
        }
        double ans = 0;
        for (i=1;i<R;i++)
            ans+=calc(Q[i-1],Q[i]);
        printf("%.2lf\n",ans);
    }



}

}}}

类似凸包的扫描方法，每次把凹的维护成凸的，就是最短距离。

#include <stdio.h>
#include <math.h>
#include <map>
#include <algorithm>
#include <string.h>
using namespace std;
double X[1000000],Y[1000000];
bool ral(int i,int j,int k){
    return (X[j]-X[i])*(Y[k]-Y[i])>(X[k]-X[i])*(Y[j]-Y[i]);
}
double calc(int i,int j){
    return sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]));
}
int Q[1000000];
int main(){
    int N,i,L,R;
    while(scanf("%d",&N)!=EOF){
        for (i=0;i<N;i++)
            scanf("%lf%lf",&X[i],&Y[i]);
        Q[0] = 0;
        L = 0,R = 1;
        for (i=1;i<N;i++)
        {
            while(L<R-1&&!ral(Q[R-2],i,Q[R-1]))
                R--;
            Q[R++] = i;
        }
        double ans = 0;
        for (i=1;i<R;i++)
            ans+=calc(Q[i-1],Q[i]);
        printf("%.2lf\n",ans);
    }
}