Doveqise

Doveqise

万事皆虚,诸行皆允

AT48 レースゲーム 题解

posted on 2019-06-30 08:13:17 | under 题解 |

这道题 一道大概暴力能过的样子
具体思路就是向上走,然后在每个点找到能到达的倾斜角 最小 和 最大 的点
然后判断哪一个点更优
然后记录答案
然后这样一直到终点
最后的路径大概就像这样(图中红线)
AT48题解图
然后再介绍一下hypot()函数
这个函数是算两点欧式几何距离哒
大概就和代码中的getdis()效果相同
不多说下面贴代码↓

#include <bits/stdc++.h>
using namespace std;
const double dis_max = 1e17;
const int maxn = 2e5 + 5;
int n, s, e;
int l[maxn], r[maxn];
double ans = 0;
double getdis(double a, double b)
{
    return sqrt(a * a + b * b);
}
void solve()
{
    l[n] = r[n] = e;
    int nowy = 0;
    double nowx = s;
    while (nowy < n)
    {
        double zuoarc = -dis_max, youarc = dis_max;
        int ly = nowy, ry = nowy;
        for (int y = nowy + 1; y <= n; y++)
        {
            double larc = (l[y] - nowx) / (y - nowy), rarc = (r[y] - nowx) / (y - nowy);
            if (larc > zuoarc)
            {
                zuoarc = larc;
                ly = y;
            }
            if (rarc < youarc)
            {
                youarc = rarc;
                ry = y;
            }
            if (zuoarc >= youarc)
            {
                if (ly < ry)
                {
                    ans += hypot/*getdis*/(l[ly] - nowx, ly - nowy);
                    nowy = ly;
                    nowx = l[ly];
                }
                else
                {
                    ans += hypot/*getdis*/(r[ry] - nowx, ry - nowy);
                    nowy = ry;
                    nowx = r[ry];
                }
                break;
            }
        }
    }
    return;
}

signed main()
{
    scanf("%d%d%d", &n, &s, &e);
    for (int i = 0; i <= n; i++)
        scanf("%d%d", &l[i], &r[i]);
    solve();
    printf("%0.14lf", ans);
    return 0;
}