team2012-F3-sol-0021

从 Trac 迁移的文章

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

原文章内容如下：

{{{
题意：给定一个折线描绘的山峰，飞机从最左1号点要开到最右n号点，不能撞到山，求最短飞行距离。
解法：求上半部分的凸包。
P.S.由于数据较弱直接模拟都能过。。比赛的时候我就水过的。。
}}}
{{{
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;

struct vec
{
    LL x, y;
    vec operator-(vec& ano)
    {
        vec ret;
        ret.x = x - ano.x;
        ret.y = y - ano.y;
        return ret;
    }
    LL cross(vec ano)
    {
        return x*ano.y - y*ano.x;
    }
}a[1000003], stk[1000003];
int n, p;

double dis(vec& a, vec& b)
{
    double dx = a.x-b.x,
           dy = a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}

int main()
{
    while(~scanf("%d", &n))
    {
        for(int i=1;i<=n;i++)
            scanf("%lld %lld", &a[i].x, &a[i].y);

        stk[1] = a[1];
        stk[2] = a[2];
        p = 2;
        for(int i=3;i<=n;i++)
        {
            while(p >= 2 && (a[i]-stk[p]).cross(stk[p]-stk[p-1]) <= 0)
                p--;
            stk[++p] = a[i];
        }
        double ans = 0;
        for(int i=2;i<=p;i++)
            ans += dis(stk[i-1], stk[i]);
        printf("%.2lf\n", ans);
    }
    return 0;
}
}}}

题意：给定一个折线描绘的山峰，飞机从最左1号点要开到最右n号点，不能撞到山，求最短飞行距离。
解法：求上半部分的凸包。
P.S.由于数据较弱直接模拟都能过。。比赛的时候我就水过的。。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
struct vec
{
    LL x, y;
    vec operator-(vec& ano)
    {
        vec ret;
        ret.x = x - ano.x;
        ret.y = y - ano.y;
        return ret;
    }
    LL cross(vec ano)
    {
        return x*ano.y - y*ano.x;
    }
}a[1000003], stk[1000003];
int n, p;
double dis(vec& a, vec& b)
{
    double dx = a.x-b.x,
           dy = a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}
int main()
{
    while(~scanf("%d", &n))
    {
        for(int i=1;i<=n;i++)
            scanf("%lld %lld", &a[i].x, &a[i].y);
        stk[1] = a[1];
        stk[2] = a[2];
        p = 2;
        for(int i=3;i<=n;i++)
        {
            while(p >= 2 && (a[i]-stk[p]).cross(stk[p]-stk[p-1]) <= 0)
                p--;
            stk[++p] = a[i];
        }
        double ans = 0;
        for(int i=2;i<=p;i++)
            ans += dis(stk[i-1], stk[i]);
        printf("%.2lf\n", ans);
    }
    return 0;
}