Submission #6258175

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<unsigned char, unsigned char> pcc;
typedef pair<double, double> pdd;
typedef vector<vector<ll>> matrix;

const long double PI = 2 * acos(0);

int dp[200005];
int lis(vector<int> v) {
  if(v.empty()) return 0;
  dp[1] = 0;
  int ret = 1;
  for(int i = 1; i < v.size(); i++) {
    int lhs = 0;
    int rhs = ret;
    while(lhs != rhs) {
      int mid = (lhs+rhs+1)/2;
      if(v[i] > v[dp[mid]]) lhs = mid;
      else rhs = mid-1;
    }
    dp[++lhs] = i;
    ret = max(ret, lhs);
  }
  return ret;
}

pii l[200005];
void solve() {
  int xa, ya, xb, yb;
  cin >> xa >> ya >> xb >> yb;
  int n;
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> l[i].first >> l[i].second;
  }
  sort(l, l+n);
  ll ret = 0;
  if(xa > xb) {
    swap(xa, xb);
    swap(ya, yb);
  }
  ret = abs(xa-xb) + abs(ya-yb);
  ret *= 100;
  bool rev = false;
  if(ya > yb) {
    swap(ya, yb);
    rev = true;
  }
  vector<int> v;
  for(int i = 0; i < n; i++) {
    if(l[i].first >= xa && l[i].first <= xb && l[i].second >= ya && l[i].second <= yb) {
      v.push_back(l[i].second);
    }
  }
  if(rev) reverse(v.begin(), v.end());
  int amt = lis(v);
  ret -= 20 * amt;
  ll pis = 5 * amt;
  if(amt == (min(yb-ya, xb-xa) + 1)) {
    pis += 5;
  }
  cout << fixed << setprecision(17) << (ret+pis*PI) << "\n";
}

void casesolve() {
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ":" << "\n";
    solve();
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  // casesolve();
}

Submission Info

Judge Result