Submission #2548819

---

Source Code Expand

//============================================================================
// Name        : training.cpp
// Author      : CoNKeR The Red Squirrel
//============================================================================
#include <bits/stdc++.h>

#define MAX_N 200005
#define INF 1000000000
#define bit(mask, i) (mask & (1<<i))

using namespace std;

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef long long ll;
typedef double lf;

lf PI = 2.0*acos(0.0);

int lis(vi &v) {
    set<int> p;
    for(int i = 0; i < (int)v.size(); ++i) {
        set<int>::iterator it = p.lower_bound(v[i]);
        if(it != p.end()) { p.erase(it); }
        p.insert(v[i]);
    }
    return p.size();
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    //freopen("acmproject.in", "r", stdin);
    //freopen("acmproject.out", "w", stdout);

    ii a, b;
    int n;
    cin>>a.first>>a.second>>b.first>>b.second>>n;
    vii fountains(n);
    while(n--) {
        cin>>fountains[n].first>>fountains[n].second;
    }
    sort(fountains.begin(), fountains.end());
    vi interval;
    if(a > b) { swap(a, b); }
    int x1 = a.first, x2 = b.first;
    int y1 = min(a.second, b.second), y2 = max(a.second, b.second);
    int c = a.second > b.second ? -1 : 1;
    for(int i =0; i < (int)fountains.size(); ++i) {
        if(fountains[i].first >= x1 && fountains[i].second >= y1 && fountains[i].first <= x2 && fountains[i].second <= y2) {
            interval.push_back(c*fountains[i].second);
        }
    }
    int l = lis(interval), x = b.first - a.first, y = abs(b.second - a.second);
    lf sol = 100.0*(lf)(x + y);
    sol += 5.0*(PI - 4.0)*(lf)l;
    if(l == min(x, y) + 1) { sol += 5.0*PI; }

    cout<<setprecision(16)<<fixed<<sol<<"\n";

    return 0;
}

Submission Info

Judge Result