Submission #1548182

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
struct LIS {
    vector<int>& v;
    vector<int> dp, id, ret, info;
    // info 1:unused 2:使っても良い 3:必ず使う
    int n, lis;
    LIS(vector<int>& _v) : v(_v) {
        n = v.size();
        dp.resize(n, INT_MAX / 2);
        id.resize(n, 0);
        rep(i, 0, n) {
            // 狭義単調増加列
            //id[i] = lower_bound(dp.begin(), dp.end(), v[i]) - dp.begin();
            // 広義単調増加列
            id[i] = upper_bound(dp.begin(), dp.end(), v[i]) - dp.begin();
            dp[id[i]] = v[i];
        }
        int nl = *max_element(id.begin(), id.end());
        lis = nl;
        ret.resize(nl + 1, 0);
        rrep(i, n - 1, 0) if (id[i] == nl) ret[nl] = v[i], nl--;

        info.resize(n);
        vector<int> ma(n + 1), cnt(n);
        ma[lis] = INT_MAX / 2;
        rrep(i, n - 1, 0) {
            // 狭義単調増加列
            //if (ma[id[i] + 1] <= v[i]) info[i] = 1;
            // 広義単調増加列
            if (ma[id[i] + 1] < v[i]) info[i] = 1;

            else cnt[id[i]]++, ma[id[i]] = max(ma[id[i]], v[i]);
        }

        rrep(i, n - 1, 0) if (info[i] == 0 && cnt[id[i]] == 1) info[i] = 3;
        rep(i, 0, n) if (info[i] == 0) info[i] = 2;
        lis--;
    }
};

/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/



double PI = 2 * acos(0.0);
typedef long long ll;
string A;
int X1, Y1, X2, Y2, N, X[201010], Y[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X1 >> Y1 >> X2 >> Y2 >> N;
    rep(i, 0, N) cin >> X[i] >> Y[i];
    if (X1 > X2) {
        X1 = 100000000 - X1;
        X2 = 100000000 - X2;
        rep(i, 0, N) X[i] = 100000000 - X[i];
    }
    if (Y1 > Y2) {
        Y1 = 100000000 - Y1;
        Y2 = 100000000 - Y2;
        rep(i, 0, N) Y[i] = 100000000 - Y[i];
    }

    vector<pair<int, int>> v;
    rep(i, 0, N) if (Y1 <= Y[i] && Y[i] <= Y2 && X1 <= X[i] && X[i] <= X2) v.push_back({ X[i], Y[i] });
    sort(v.begin(), v.end());

    vector<int> vv;
    vv.push_back(-1);
    fore(p, v) vv.push_back(p.second);
    vv.push_back(INT_MAX / 2 - 1);
    LIS lis(vv);

    double ans = 100.0 * (X2 - X1 + Y2 - Y1);
    ans += (5.0 * PI - 20.0) * lis.lis;
    if (lis.lis == min(X2 - X1, Y2 - Y1) + 1) ans += 5.0 * PI;
    printf("%.15f\n", ans);
}

Submission Info

Judge Result