team2012-E1-mysol-0021

从 Trac 迁移的文章

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

原文章内容如下：

{{{
/* 解题报告 //

给定一条折线，问从折线起点到终点，从折线上方走的最短路是多长

按照 x 从小到大的顺序依次加点，维护一个上凸壳，具体做法就是：
如果『倒数第二个点，倒数第一个点，即将要加入的点』形成 V 字形
则删除倒数第一个点，并重新回到上一步继续检查

// By 猛犸也钻地 @ 2012.07.26 */
}}}

{{{
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

typedef pair<int,int> PII;
#define x first
#define y second

int main(){
    int n;
    PII a,b,c;
    while(scanf("%d",&n)==1){
        vector<PII> u;
        for(int i=0;i<n;i++){
            scanf("%d%d",&c.x,&c.y);
            while(u.size()>=2){
                PII a=u[u.size()-2];
                PII b=u[u.size()-1];
                if(double(c.x-a.x)*(b.y-a.y)>=double(b.x-a.x)*(c.y-a.y)) break;
                u.pop_back();
            }
            u.push_back(PII(c.x,c.y));
        }
        double ans=0;
        for(size_t i=1;i<u.size();i++){
            double dx=u[i].x-u[i-1].x;
            double dy=u[i].y-u[i-1].y;
            ans+=sqrt(dx*dx+dy*dy);
        }
        printf("%.2f\n",ans);
    }
}
}}}

/* 解题报告 //
给定一条折线，问从折线起点到终点，从折线上方走的最短路是多长
按照 x 从小到大的顺序依次加点，维护一个上凸壳，具体做法就是：
如果『倒数第二个点，倒数第一个点，即将要加入的点』形成 V 字形
则删除倒数第一个点，并重新回到上一步继续检查
// By 猛犸也钻地 @ 2012.07.26 */

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
int main(){
    int n;
    PII a,b,c;
    while(scanf("%d",&n)==1){
        vector<PII> u;
        for(int i=0;i<n;i++){
            scanf("%d%d",&c.x,&c.y);
            while(u.size()>=2){
                PII a=u[u.size()-2];
                PII b=u[u.size()-1];
                if(double(c.x-a.x)*(b.y-a.y)>=double(b.x-a.x)*(c.y-a.y)) break;
                u.pop_back();
            }
            u.push_back(PII(c.x,c.y));
        }
        double ans=0;
        for(size_t i=1;i<u.size();i++){
            double dx=u[i].x-u[i-1].x;
            double dy=u[i].y-u[i-1].y;
            ans+=sqrt(dx*dx+dy*dy);
        }
        printf("%.2f\n",ans);
    }
}