Submission #1591760

---

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;
}
 
bool f_type = false;
 
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));
        }
    }
 
    if((xi < x2 and yi < y2) or (xi > x2 and yi > y2))
        f_type = true;
 
 
    if(f_type) sort(A.begin(), A.end());
    else sort(A.begin(), A.end(), greater<pair<int, int> >());
 
    int length = LIS(), tlength;
 
    cout << fixed << setprecision(15);
 
    long long tans = (abs(xi-x2)+abs(yi-y2))*100;
 

/*    if(f_type) tlength = abs(yi-y2)+1;
    else tlength = abs(xi-x2)+1;
*/

   tlength = min(abs(xi-x2)+1, abs(yi-y2)+1);
 
    if(xi == x2) tlength = 1;
    if(yi == y2) tlength = 1;
 
    if(length == tlength) {
        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