Submission #1540657

---

Source Code Expand

#pragma comment(linker, "/STACK:512000000")
#define _CRT_SECURE_NO_WARNINGS
//#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
void solve(bool);
void precalc();
clock_t start;
int main() {
#ifdef AIM
  freopen("/home/alexandero/ClionProjects/ACM/input.txt", "r", stdin);
  //freopen("/home/alexandero/ClionProjects/ACM/output.txt", "w", stdout);
  //freopen("out.txt", "w", stdout);
#else
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
#endif
  start = clock();
  int t = 1;
  cout.sync_with_stdio(0);
  cin.tie(0);
  precalc();
  cout.precision(10);
  cout << fixed;
  //cin >> t;
  int testNum = 1;
  while (t--) {
    //cout << "Case #" << testNum++ << ": ";
    //cerr << testNum << endl;
    solve(true);
    //cerr << testNum - 1 << endl;
  }
  cout.flush();
#ifdef AIM1
  while (true) {
      solve(false);
  }
#endif

#ifdef AIM
  cerr << "\n\n time: " << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n";
#endif

  return 0;
}

//BE CAREFUL: IS INT REALLY INT?

template<typename T>
T binpow(T q, T w, T mod) {
  if (!w)
    return 1 % mod;
  if (w & 1)
    return q * 1LL * binpow(q, w - 1, mod) % mod;
  return binpow(q * 1LL * q % mod, w / 2, mod);
}

template<typename T>
T gcd(T q, T w) {
  while (w) {
    q %= w;
    swap(q, w);
  }
  return q;
}
template<typename T>
T lcm(T q, T w) {
  return q / gcd(q, w) * w;
}

template <typename T>
void make_unique(vector<T>& a) {
  sort(all(a));
  a.erase(unique(all(a)), a.end());
}

void precalc() {

}

template<typename T>
void relax_min(T& cur, T val) {
  cur = min(cur, val);
}

template<typename T>
void relax_max(T& cur, T val) {
  cur = max(cur, val);
}

#define int li
//const int mod = 1000000007;

void solve(bool read) {
    int x[2], y[2];
    cin >> x[0] >> y[0] >> x[1] >> y[1];
    if (make_pair(x[0], y[0]) > make_pair(x[1], y[1])) {
        swap(x[0], x[1]);
        swap(y[0], y[1]);
    }

    int n;
    cin >> n;
    vector<pair<int, int>> points;
    for (int i = 0; i < n; ++i) {
        int X, Y;
        cin >> X >> Y;
        if (X < x[0] || X > x[1] || Y < min(y[0], y[1]) || Y > max(y[1], y[0])) {
            continue;
        }
        points.push_back({X, Y});
    }

    sort(all(points));

    vector<int> res(n + 1, (int)1e18);
    res[0] = -1;
    for (auto item : points) {
        int id = lower_bound(all(res), item.second) - res.begin();
        res[id] = item.second;
    }

    int best = 0;
    for (int i = res.size() - 1; i >= 0; --i) {
        if (res[i] < 2e9) {
            best = i;
            break;
        }
    }

    //cout << best << endl;

    if (x[0] == x[1] || y[0] == y[1]) {
        double ans = (abs(x[0] - x[1]) + abs(y[0] - y[1])) * 100 + (10 * acos(-1.0) - 20) * best;
        cout << ans << endl;
        return;
    }

    double ans = (abs(x[0] - x[1]) + abs(y[0] - y[1])) * 100 + (5 * acos(-1.0) - 20) * best;

    cout << ans << endl;

}

Submission Info

Judge Result