Atcoder Grand Contest 019 C. Fountain Walk

Atcoder Grand Contest 019 C. Fountain Walk

感想

500点くらいの問題

解法

一般性を失わずに左上にスタート、右下にゴールがあると仮定して、それらを頂点とする長方形を考える。このとき、明らかにこの長方形の外に出て遠回りする方が経路長が短くなるようなことはない。

この長方形の内部で移動することを考えるときに、できるだけ(↓, 噴水, →）という移動をすればよいはずである。ただしこの移動をするために遠回りする必要はなく、まず通過できる噴水の最大値を$\ LIS\ $で求める。さらに図を書いて実験すると、条件を満たすような噴水の置き方の中で、最大個数、すなわち$\ min(gy - sy, gx - sx) + 1\ $個より少ない場合は、通過可能なすべての噴水をこの移動の仕方に使うことができる。$\ min(gy - sy, gx - sx) + 1\ $に等しい場合は、一回だけ噴水を通過して180度回るような移動をしなければいけない（これが最適）。ここを場合分けして素直に計算すればよい。

スタートの位置とゴールの位置は実際には異なるので、うまく処理する。

実装

#include "bits/stdc++.h"
using namespace std;

#define all(x)  x.begin(), x.end()

static const int INF = 1 << 30;
static const double PI = acos(-1);

int dp[202020];

int main() {
        int sx, sy, gx, gy;
        scanf("%d%d%d%d", &sx, &sy, &gx, &gy);
        int n;
        scanf("%d", &n);
        vector<pair<int, int>> p(n), q;
        for (int i = 0; i < n; i ++) scanf("%d%d", &p[i].first, &p[i].second);
        for (int i = 0; i < n; i ++) {
                if (min(sx, gx) <= p[i].first && p[i].first <= max(sx, gx) && min(sy, gy) <= p[i].second && p[i].second <= max(sy, gy)) {
                        q.push_back(p[i]);
                }
        }
        if (sy > gy) for (int i = 0; i < q.size(); i ++) q[i].second *= -1;
        sort(all(q));
        if (sx > gx) reverse(all(q));
        for (int i = 0; i < 202020; i ++) dp[i] = INF;
        for (int i = 0; i < q.size(); i ++) {
                *lower_bound(dp, dp + 202020, q[i].second) = q[i].second; 
        }
        int len = lower_bound(dp, dp + 202020, INF) - dp;
        double ans = (long long) (abs(gy - sy) + abs(gx - sx)) * 100;
        if (len < min(abs(gy - sy), abs(gx - sx)) + 1) {
                ans -= (20.0 - 5.0 * PI) * len;
        } else {
                ans -= (20.0 - 5.0 * PI) * (len - 1);
                ans += 10.0 * PI - 20;
        }
        printf("%.15lf\n", ans);
        return 0;
}