2012-A3-0021

从 Trac 迁移的文章

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

原文章内容如下：

题意:要从一条x坐标严格递增的折段一端走到另一端，只能经过上侧而不能穿越它，求最短路径长度。

最短路径显然是它的上凸包络线，于是只要按顺序一条条吧线段加入，用维护严格凸的折线段的栈就可以了。


{{{
#include<cstdio>
#include<cmath>
typedef double real;
typedef long long num;
size_t stack[1<<20],n,ps;
int x[1<<20],y[1<<20];

void push(size_t i){
    stack[++ps]=i;
}
void pop(){--ps;}
bool convex(size_t i,size_t j,size_t k){
    num
    xx1=(num)x[j]-x[i],
    yy1=(num)y[j]-y[i],
    xx2=(num)x[k]-x[i],
    yy2=(num)y[k]-y[i];
    return xx1*yy2>=xx2*yy1;
}
real dist(size_t i,size_t j){
    return hypot(x[i]-x[j],y[i]-y[j]);
}
int main(){

    for(real ans;scanf("%d",&n)==1;printf("%.2lf\n",ans)){
        for(size_t i=0;i<n;++i)
            scanf("%d%d",x+i,y+i);

        ps=0;push(0);push(1);
        for(size_t i=2;i<n;++i){
            for(;ps>1 && convex(stack[ps-1],stack[ps],i);)pop();
            push(i);
        }
        ans =0;
        for(size_t i=1;i<ps;++i)
            ans += dist(stack[i],stack[i+1]);
    }
}
}}}

题意:要从一条x坐标严格递增的折段一端走到另一端，只能经过上侧而不能穿越它，求最短路径长度。

最短路径显然是它的上凸包络线，于是只要按顺序一条条吧线段加入，用维护严格凸的折线段的栈就可以了。

#include<cstdio>
#include<cmath>
typedef double real;
typedef long long num;
size_t stack[1<<20],n,ps;
int x[1<<20],y[1<<20];
void push(size_t i){
    stack[++ps]=i;
}
void pop(){--ps;}
bool convex(size_t i,size_t j,size_t k){
    num
    xx1=(num)x[j]-x[i],
    yy1=(num)y[j]-y[i],
    xx2=(num)x[k]-x[i],
    yy2=(num)y[k]-y[i];
    return xx1*yy2>=xx2*yy1;
}
real dist(size_t i,size_t j){
    return hypot(x[i]-x[j],y[i]-y[j]);
}
int main(){
    for(real ans;scanf("%d",&n)==1;printf("%.2lf\n",ans)){
        for(size_t i=0;i<n;++i)
            scanf("%d%d",x+i,y+i);
        ps=0;push(0);push(1);
        for(size_t i=2;i<n;++i){
            for(;ps>1 && convex(stack[ps-1],stack[ps],i);)pop();
            push(i);
        }
        ans =0;
        for(size_t i=1;i<ps;++i)
            ans += dist(stack[i],stack[i+1]);
    }
}