Submission #1546531

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

int main()
{
    using pii = pair<int, int>;
    int x1, y1, x2, y2;
    int N;
    cin >> x1 >> y1 >> x2 >> y2 >> N;

    int sx = min(x1, x2), tx = max(x1, x2);
    int sy = min(y1, y2), ty = max(y1, y2);
    
    vector<pii> v;
    vector<int> X(N), Y(N);
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i];
        if (sx <= X[i] && X[i] <= tx && sy <= Y[i] && Y[i] <= ty) {
            v.emplace_back(X[i], Y[i]);
        }
    }

    int n = v.size();
    if (x1 > x2) {
        swap(x1, x2);
        for (int i = 0; i < n; i++) {
            v[i].first *= -1;
        }
    }

    if (y1 > y2) {
        swap(y1, y2);
        for (int i = 0; i < n; i++) {
            v[i].second *= -1;
        }
    }
    sort(v.begin(), v.end());

    constexpr int INF = 1145141919;

    vector<int> dp(n, INF);
    for (int i = 0; i < n; i++) {
        int c = v[i].second;
        *lower_bound(dp.begin(), dp.end(), c) = c;
    }

    constexpr double PI = acos(-1);
    int m = lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
    double ans = (tx - sx + ty - sy) * 100.0 - (20.0 - 5.0 * PI) * m;
    if (min(tx - sx, ty - sy) + 1 == m) {
        ans += 5 * PI;
    }
    printf("%.15f\n", ans);    
    return 0;
}

Submission Info

Judge Result