Submission #1545950

---

Source Code Expand

#include <bits/stdc++.h>

#define FOR(i, a, b)  for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << "\n"
#define _ << " _ " <<
#define ll long long
#define pii pair <int, int>
#define ld long double

using namespace std;

ld fontana = (((ld) 20.0 * (ld) 3.141592653589793238462643383279) / (ld) 4.0);

vector <pii> ve;
bool flag;

bool cmp(pii a, pii b) {
  if (flag) return a.first > b.first;
  return a.first < b.first;
}

unordered_map <int, int> loga;

void add(int x, int v) {
  for (x; x <= 1e8; x += x & -x) {
    loga[x] = max(loga[x], v);
  }
  return;
}

int val(int x) {
  int tr = 0;
  for (x; x; x -= x & -x) {
    tr = max(tr, loga[x]);
  }
  return tr;
}

int main() {
  ios_base::sync_with_stdio(false);

  int x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  x1++; y1++; x2++; y2++;

  if (x1 > x2) {
    swap(x1, x2);
    swap(y1, y2);
  }
  if (y1 > y2) flag = 1;

  int n;
  cin >> n;
  REP(i, n) {
    int x, y;
    cin >> x >> y;
    x++; y++;
    if (x < min(x1, x2) || x > max(x1, x2)) continue;
    if (y < min(y1, y2) || y > max(y1, y2)) continue;
    ve.push_back({x, y});
  }
  sort(ve.begin(), ve.end(), cmp);

  ld out = ((ld)(abs(x2 - x1)) * (ld) 100) + ((ld)(abs(y2 - y1)) * (ld) 100);

  int ma = 0;
  REP(i, ve.size()) {
    int x = ve[i].first;
    int y = ve[i].second;

    int tr = val(y);
    ma = max(ma, tr + 1);
    add(y, tr + 1);
  }
  out -= (ld) ma * (ld) 20;
  out += (ld) ma * fontana;
  if (ma > min(abs(x2 - x1), abs(y2 - y1))) {
    out += fontana;
  }


  cout << fixed << setprecision(15) << out << "\n";

  return 0;
}

Submission Info

Judge Result