Submission #4325867

---

Source Code Expand

// includes {{{
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
// #include<deque>
// #include<multiset>
// #include<bitset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

const int N = 2e5 + 10;
int fromX, fromY, toX, toY;
int n;
int x[N], y[N];

// SegmentTree( size [, initial] )
// SegmentTree( <data> )
/// --- SegmentTree {{{ ///
#include <cassert>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <vector>
template < class Monoid >
struct SegmentTree {
private:
  using T = typename Monoid::T;
  size_t n;
  vector< T > data;
  // call after touch data[i]
  void prop(int i) { data[i] = Monoid::op(data[2 * i], data[2 * i + 1]); }

public:
  SegmentTree() : n(0) {}
  SegmentTree(int n, T initial = Monoid::identity()) : n(n) {
    data.resize(n * 2, initial);
    for(int i = n - 1; i > 0; i--) data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]);
  }
  template < class InputIter, class = typename iterator_traits< InputIter >::value_type >
  SegmentTree(InputIter first, InputIter last) : SegmentTree(distance(first, last)) {
    copy(first, last, begin(data) + n);
    // fill from deep
    for(int i = n - 1; i > 0; i--) prop(i);
  }
  SegmentTree(vector< T > v) : SegmentTree(v.begin(), v.end()) {}
  SegmentTree(initializer_list< T > v) : SegmentTree(v.begin(), v.end()) {}
  void set(size_t i, const T &v) {
    assert(i < n);
    data[i += n] = v;
    while(i >>= 1) prop(i); // propUp
  }
  T get(size_t i) {
    assert(i < n);
    return data[i + n];
  }
  T query(int l, int r) {
    if(l < 0) l = 0;
    if(l >= r) return Monoid::identity();
    if(r > (int) n) r = n;
    T tmpL = Monoid::identity(), tmpR = Monoid::identity();
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if(l & 1) tmpL = Monoid::op(tmpL, data[l++]);
      if(r & 1) tmpR = Monoid::op(data[--r], tmpR);
    }
    return Monoid::op(tmpL, tmpR);
  }
  inline void dum(int r = -1) {
#ifdef DEBUG
    if(r < 0) r = n;
    DEBUG_OUT << "{";
    for(int i = 0; i < min(r, (int) n); i++) DEBUG_OUT << (i ? ", " : "") << get(i);
    DEBUG_OUT << "}" << endl;
#endif
  }
};
/// }}}--- ///

/// --- Monoid examples {{{ ///
constexpr long long inf = 1e18 + 100;
#include <algorithm>
struct Nothing {
  using T = char;
  using Monoid = Nothing;
  using M = T;
  static constexpr T op(const T &, const T &) { return T(); }
  static constexpr T identity() { return T(); }
  template < class X >
  static constexpr X actInto(const M &, ll, ll, const X &x) {
    return x;
  }
};

template < class U = long long >
struct RangeMin {
  using T = U;
  static T op(const T &a, const T &b) { return min(a, b); }
  static constexpr T identity() { return T(inf); }
};

template < class U = long long >
struct RangeMax {
  using T = U;
  static T op(const T &a, const T &b) { return max(a, b); }
  static constexpr T identity() { return -T(inf); }
};

template < class U = long long >
struct RangeSum {
  using T = U;
  static T op(const T &a, const T &b) { return a + b; }
  static constexpr T identity() { return T(0); }
};

template < class U >
struct RangeProd {
  using T = U;
  static T op(const T &a, const T &b) { return a * b; }
  static constexpr T identity() { return T(1); }
};

template < class U = long long >
struct RangeOr {
  using T = U;
  static T op(const T &a, const T &b) { return a | b; }
  static constexpr T identity() { return T(0); }
};

#include <bitset>

template < class U = long long >
struct RangeAnd {
  using T = U;
  static T op(const T &a, const T &b) { return a & b; }
  static constexpr T identity() { return T(-1); }
};

template < size_t N >
struct RangeAnd< bitset< N > > {
  using T = bitset< N >;
  static T op(const T &a, const T &b) { return a & b; }
  static constexpr T identity() { return bitset< N >().set(); }
};

/// }}}--- ///

using Seg = SegmentTree< RangeMax<> >;

// constructor(H)
// index(y, x)
// === init(doUnique) ===
// set(y, x, val)         // index(y, x) must be done
// query(yl, yr, xl, xr)
// === --- ===
// only offline
/// --- Fractional Cascading SegmentTree {{{ ///
#include <algorithm>
#include <cassert>
#include <functional>
#include <map>
#include <vector>

template < class T, class U, bool yCompress = true, class Index = ll>
struct FractionalCascadingSegmentTree {
  size_t h;
  vector< T > dat;
  vector< vector< Index > > indices;
  vector< vector< size_t > > L, R;
  U identity;
  function< void(T &, int x, const U &) > setX;
  function< void(T &, vector< Index > &) > initX;
  function< U(T &, int x1, int x2) > queryX;
  function< U(const U &, const U &) > mergeY;
  FractionalCascadingSegmentTree() {}
  FractionalCascadingSegmentTree(size_t tempH, //
                                 const function< void(T &, int, const U &) > &setX,
                                 const function< void(T &, vector< Index > &) > &initX,
                                 const function< U(T &, int, int) > &queryX,
                                 const function< U(const U &, const U &) > &mergeY,
                                 U identity = U(), T initial = T())
      : identity(identity), setX(setX), initX(initX), queryX(queryX), mergeY(mergeY) {
    h = 1;
    while(h < tempH) h <<= 1;
    dat = vector< T >(2 * h, initial);
    indices = vector< vector< Index > >(2 * h);
    L = R = vector< vector< size_t > >(2 * h);
  }
  vector< Index > ys;
  map<Index, int> ymap;
  vector< pair< Index, Index > > pre_indecies;
  void index(Index i, Index j) {
    if(yCompress) {
      ys.push_back(i);
      pre_indecies.emplace_back(i, j);
    } else {
      size_t i2 = i;
      assert(i2 < h);
      indices[i2 + h].push_back(j);
    }
  }
  void init(bool doUnique) {
    if(yCompress) {
      sort(begin(ys), end(ys));
      ys.erase(unique(begin(ys), end(ys)), end(ys));
      {
        size_t i = 0;
        for(Index &y : ys) ymap[y] = i++;
      }
      for(pair< Index, Index > idx : pre_indecies) {
        indices[ymap[idx.first] + h].push_back(idx.second);
      }
    }
    for(size_t i = h; i < h * 2; i++) {
      sort(begin(indices[i]), end(indices[i]));
      if(doUnique)
        indices[i].erase(unique(begin(indices[i]), end(indices[i])), end(indices[i]));
      initX(dat[i], indices[i]);
    }
    for(size_t i = h - 1; i >= 1; i--) {
      size_t lsz = indices[i * 2].size();
      size_t rsz = indices[i * 2 + 1].size();
      size_t nsz = lsz + rsz;
      indices[i].resize(nsz);
      L[i].resize(nsz + 1, lsz);
      R[i].resize(nsz + 1, rsz);
      size_t p1 = 0, p2 = 0;
      while(p1 < lsz || p2 < rsz) {
        L[i][p1 + p2] = p1;
        R[i][p1 + p2] = p2;
        if(p1 < lsz && (p2 == rsz || indices[i * 2][p1] <= indices[i * 2 + 1][p2])) {
          indices[i][p1 + p2] = indices[i * 2][p1];
          p1++;
        } else {
          indices[i][p1 + p2] = indices[i * 2 + 1][p2];
          p2++;
        }
      }
      initX(dat[i], indices[i]);
    }
  }

public:
  void set(Index y, Index x, const U &val) {
    if(yCompress) {
      assert(ymap.count(y));
      _set(ymap[y], x, val);
    } else {
      size_t y2 = y;
      assert(y2 < h);
      _set(y2, x, val);
    }
  }

private:
  void _set(size_t y, Index x, const U &val) {
    size_t lower = lower_bound(begin(indices[1]), end(indices[1]), x) - begin(indices[1]);
    assert(lower < indices.size());
    size_t k = 1, l = 0, r = h;
    while(k != y + h) {
      setX(dat[k], lower, val);
      size_t mid = (l + r) >> 1;
      if(y < mid) {
        lower = L[k][lower];
        k = k * 2;
        r = mid;
      } else {
        lower = R[k][lower];
        k = k * 2 + 1;
        l = mid;
      }
    }
    setX(dat[k], lower, val);
    assert(indices[k][lower] == x);
  }

public:
  U query(Index a, Index b, Index l, Index r) {
    if(a >= b || l >= r) return identity;
    size_t lower = lower_bound(begin(indices[1]), end(indices[1]), l) - begin(indices[1]);
    size_t upper = lower_bound(begin(indices[1]), end(indices[1]), r) - begin(indices[1]);
    size_t a2, b2;
    if(yCompress) {
      a2 = lower_bound(begin(ys), end(ys), a) - begin(ys);
      b2 = lower_bound(begin(ys), end(ys), b) - begin(ys);
    } else {
      a2 = a, b2 = b;
      assert(a2 < h && b2 <= h);
    }
    return query(a2, b2, lower, upper, 0, h, 1);
  }

private:
  U query(size_t a, size_t b, size_t lower, size_t upper, size_t l, size_t r, size_t k) {
    if(lower == upper) return identity;
    if(b <= l || r <= a) return identity;
    if(a <= l && r <= b) return queryX(dat[k], lower, upper);
    return mergeY(query(a, b, L[k][lower], L[k][upper], l, (l + r) >> 1, k * 2),
                  query(a, b, R[k][lower], R[k][upper], (l + r) >> 1, r, k * 2 + 1));
  }
};

/// }}}--- ///

// never forget to init SparseTable by yourself
// FC-SegmentTree Example {{{

using Under = Seg;
using Value = RangeMax<>;
using Data = Value::T;

FractionalCascadingSegmentTree< Under, Data, 1 > ecas(
    N + 1,
    // set x
    [](Under &dat, int x, const Data &val) -> void {
      // dat.set(x, Value::op(dat.get(x), val));
      dat.set(x, val);
    },
    // init x
    [](Under &dat, const vector< ll > &indices) -> void {
      dat = Under(indices.size(), 0); // serve initial?
    },
    // query [l, r) // l < r
    [](Under &dat, int l, int r) -> Data { return dat.query(l, r); },
    // merge y-direction
    [](Data a, Data b) -> Data { return max(a, b); }
    // optional
    ,
    0);
// }}}

// uniq, compress {{{
#include <algorithm>
#include <map>
#include <vector>
template < class T >
void uniq(vector< T > &v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
template < class T >
map< T, int > compress(const vector< T > &v) {
  map< T, int > mp;
  int i = -1;
  for(auto &e : v) mp[e] = ++i;
  return mp;
}
// }}}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> fromX >> fromY >> toX >> toY;
  cin >> n;
  bool revX = 0, revY = 0;
  if(fromX > toX) fromX *= -1, toX *= -1, revX = 1;
  if(fromY > toY) fromY *= -1, toY *= -1, revY = 1;
  using P = pair< int, int >;
  vector< P > v;
  toX -= fromX, toY -= fromY;
  for(int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
    if(revX) x[i] *= -1;
    if(revY) y[i] *= -1;
    x[i] -= fromX;
    y[i] -= fromY;
    if(0 <= x[i] && x[i] <= toX && 0 <= y[i] && y[i] <= toY) {
      ecas.index(x[i], y[i]);
      v.emplace_back(x[i], y[i]);
    }
  }
  fromX = fromY = 0;

  sort((v).begin(), (v).end());

  ecas.init(1);

  for(auto p : v) {
    int val = ecas.query(0, p.first, 0, p.second) + 1;
    ecas.set(p.first, p.second, val);
  }

  cout << fixed << setprecision(20);
  constexpr double PI = acos(-1);
  constexpr double A = 20 - 5 * PI;
  constexpr double B = 10 * PI - 20;

  int num = ecas.query(0, toX + 1, 0, toY + 1);

  double ans = 0;
  if(min(toX, toY) + 1 != num) {
    ans += (double) -num * A;
    ans += 100.0 * (toX + toY);
  } else {
    ans -= (double) A * (num - 1);
    ans += B;
    ans += (toX + toY) * 100.0;
  }

  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result