Submission #1793055

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;
 
constexpr int INF = 1e9;
constexpr ld pi = acos(-1);
 
int main() {
    int sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    if(sx >= gx && sy >= gy) {
        swap(sx, gx);
        swap(sy, gy);
    }
    int lx = min(sx, gx);
    int ly = min(sy, gy);
    int rx = max(sx, gx);
    int ry = max(sy, gy);
    int N;
    cin >> N;
    vector<pii> v(N);
    ld res = abs(sx - gx) + abs(gy - sy);
    res *= 100;
    int dummy;
    bool f = false;
    for(int i = 0; i < N; ++i) {
        cin >> v[i].first >> v[i].second;
        if(sx == gx && sx == v[i].first && ly <= v[i].second && v[i].second <= ry || sy == gy && lx <= v[i].first && v[i].first <= rx && v[i].second == sy) {
            f = true;
        }
        if(sx <= gx && sy <= gy) {
            dummy = INF;
            continue;
        } else if(sx <= gx && sy >= gy) {
            v[i].second = -v[i].second;
            dummy = 1;
        } else if(sx >= gx && sy <= gy) {
            v[i].first = -v[i].first;
            dummy = INF;
        } else {
            v[i].first = -v[i].first;
            v[i].second = -v[i].second;
            dummy = 1;
        }
    }
    if(f) {
        res += 20.0 * (pi / 2 - 1);
        cout << fixed << setprecision(12) << res << endl;
        return 0;
    }
    sort(v.begin(), v.end());
    vector<int> LIS(N, dummy);
    for(auto& p : v) {
        if(lx <= abs(p.first) && abs(p.first) <= rx && ly <= abs(p.second) && abs(p.second) <= ry) {
            *lower_bound(LIS.begin(), LIS.end(), p.second) = p.second;
        }
    }
    int cnt = find(LIS.begin(), LIS.end(), dummy) - LIS.begin();
    if(cnt == ry - ly + 1 || cnt == rx - lx + 1) {
        cnt--;
        res += 20.0 * (pi / 2 - 1);
    }
    //cout << "cnt: " << cnt << endl;
    res -= 20.0 * cnt * (1.0 - pi / 4.0);
    cout << fixed << setprecision(12) << res << endl;
}

Submission Info

Judge Result