Submission #1570344

---

Source Code Expand

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

long long xi, yi, x2, y2, N, x, y;
vector<pair<int, int> > A;
int dp[1<<20];

const long double pi = 3.141592653589793;

bool inside() {
    if(x < min(xi, x2)) return false;
    if(x > max(xi, x2)) return false;
    if(y < min(yi, y2)) return false;
    if(y > max(yi, y2)) return false;
    return true;
}

int LIS() {
    if((int)A.size() == 0)
        return 0;

    dp[0] = A[0].second;
    int C = 1;

    for(int i = 1;i < (int)A.size();i++) {
        if(A[i].second > dp[C-1]) {
            dp[C++] = A[i].second;
            continue;
        }

        dp[lower_bound(dp, dp+C, A[i].second)-dp] = A[i].second;
    }

    return C;
}

int main() {
//    freopen("input.in","r",stdin);
//    freopen("output.out","w",stdout);

    cin>>xi>>yi>>x2>>y2;
    cin>>N;
    for(int i = 0;i < N;i++) {
        cin>>x>>y;
        if(inside()) {
            A.push_back(make_pair(x, y));
        }
    }

    sort(A.begin(), A.end());
    int length = LIS();

    cout << fixed << setprecision(15);

    long long tans = (abs(xi-x2)+abs(yi-y2))*100;

    if(length == abs(yi-y2)+1) {
        cout << tans + (10*pi-20) + (5*pi-20)*(length-1) << endl;
    } else {
        cout << tans + (5*pi-20)*(length) << endl;
    }

    return 0;
}

Submission Info

Judge Result