Submission #1550018

---

Source Code Expand

    #include <bits/stdc++.h>
    using namespace std;
    using ll = long long;
    using vl = vector<ll>;
    using vvl = vector<vl>;
    using pll = pair<ll,ll>;
    using vb = vector<bool>;
    const ll oo = 0x3f3f3f3f3f3f3f3fLL;
    const double eps = 1e-9;
    #define sz(c) ll((c).size())
    #define all(c) begin(c),end(c)
    #define mp make_pair
    #define mt make_tuple
    #define pb push_back
    #define eb emplace_back
    #define xx first
    #define yy second
    #define has(c,i) ((c).find(i) != end(c))
    #define FOR(i,a,b) for (int i=(a); i<(b); i++)
    #define FORD(i,a,b) for (int i=int(b)-1; i>=(a); i--)
     
    template<typename T, typename U> struct segtree {
      ll n, H = 0;
     
      T zero;
      vector<T> value;
     
      U noop;
      vb dirty;
      vector<U> prop;
     
      segtree(T zero = T(), U noop = U()): zero(zero), noop(noop) { }
     
      void init(vector<T> &leaves) { // Array initialisieren, O(n) // TODO provate public
        n = sz(leaves);
        while ((1 << H) < 2*n) H++;
        value.resize(2*n,zero);
        dirty.resize(n);
        prop.resize(n,noop);
        copy(all(leaves),begin(value)+n);
        FORD(i,1,n) value[i] = value[2*i] + value[2*i+1];
      }
     
      void apply(ll i, U &upd) {
        value[i] = upd(value[i]);
        if (i < n) prop[i] = prop[i] + upd, dirty[i] = true;
      }
     
      void rebuild(ll i) {
        for (i /= 2; i; i /= 2) value[i] = prop[i](value[2*i] + value[2*i+1]);
      }
     
      void propagate(ll i) {
        FORD(h,1,H+1) if (dirty[i >> h]) {
          ll j = i >> h;
          apply(2*j,prop[j]), apply(2*j+1,prop[j]);
          prop[j] = noop, dirty[j] = false;
        }
      }
     
      void update(ll i, ll j, U upd) { // Update mit upd auf Intervall [i,j)
        if (i == j) return;            // (für Punkt-Update bei i setze j = i+1)
        i += n, j += n;
        propagate(i), propagate(j-1);
        for (ll l = i, r = j; l < r; l /= 2, r /= 2) {
          if (l & 1) apply(l++,upd);
          if (r & 1) apply(--r,upd);
        }
        rebuild(i), rebuild(j-1);
      }
     
      T query(ll i, ll j) { // Query auf Intervall [i,j)
        if (i == j) return zero;
        i += n, j += n;
        propagate(i), propagate(j-1);
        T resl = zero, resr = zero;
        for (; i < j; i /= 2, j /= 2) {
          if (i & 1) resl = resl + value[i++];
          if (j & 1) resr = value[--j] + resr;
        }
        return resl + resr;              //  Erforderliche Eigenschaften:
      }                                  //  1. (T,+,zero) Monoid
    };                                   //  2. (U,+,noop) Monoid
                                         //  3. noop(n) == n
    struct node {
     ll v = 0;           //  4. (u + v)(n) == v(u(n))
     node(ll x = 0) : v(x){}
      node operator+(node n) {return node(max(v, n.v));}         //  5. u(n + o) == u(n) + u(o)  (*)
    };                                   //
    struct update {                      //  Monoid: assoziative Verknüpfung
    	ll v = 0;
    	update(ll x = 0): v(x){}
      node operator()(node n) { return node(max(v, n.v)); }        //          mit neutralem Element
      update operator+(update u) { return update(max(v,u.v)); }     //          (z.B. min,+,*,gcd)
    };
     
     
    int main() {
    	const long double ARC = atan(1) * 4 * 5;
     
    	ll x1, y1, x2, y2, NN;
    	cin >> x1 >> y1 >> x2 >> y2 >> NN;
    	vector<pll> v(NN);
    	FOR(i,0,NN) cin >>v[i].first >> v[i].second;
     
    	// speccial case
    	if (x1 > x2) {
    		swap(x1, x2);
    		swap(y1, y2);
    	}
    	if (y1 > y2) {
    		y2 = y1 - y2;

    		FOR(i,0,NN) v[i].second = y1 - v[i].second;
    		y1 = 0;
    	}
     
    	if (x1 == x2) {
    		long double doof = 0;
    		FOR(i,0,NN) if (v[i].first == x1 && v[i].second > y1 && v[i].second < y2) doof = 2 * ARC  - 20;
    		printf("%.*Lf\n", 18, 100 * (y2 - y1) + doof);
    		return 0;
    	}
    	if (y1 == y2) {
    		long double doof = 0;
    		FOR(i,0,NN) if (v[i].second == y1 && v[i].first > x1 && v[i].first < x2) doof = 2 * ARC  - 20;
    		printf("%.*Lf\n", 18, 100 * (x2 - x1) + doof);
    		return 0;
    	}
    	sort(all(v));
     
    	vector<pll> choose, copied;
    	int idx = 0;
     
    	while (idx < NN && v[idx].first < x1) idx++;
    	int smallest = idx;
    	while (idx < NN && v[idx].first <= x2) {
    		if (v[idx].second >= y1 && v[idx].second <= y2) {
    			choose.pb(mp(v[idx].second, copied.size()));
    			copied.pb(v[idx]);
    		}
    		idx++;
    	}
    	int greatest =idx;
    	ll N = choose.size();
    	vl revi(N);
     
     
    	sort(all(choose));
    	FOR(i,0,N) revi[choose[i].second] = i;
    	segtree<node, update> tree;
     
    	vector<node> nice(N+5); // TODO
     
    	tree.init(nice);
     
     
    	ll best = 0;
    	FORD(i,0,N) { // iterate copieed
    		ll real = revi[i]; // idx in sorted by y (in choose)
    		ll bestVorher = tree.query(real, N).v;
    		bestVorher++;
    		nice[i] = bestVorher;
    		best = max(best, bestVorher);
    		tree.update(real, real+1, bestVorher);
    	}
     
    	long double kack = 0;
    	if (best == min(x2-x1+1, y2-y1+1)) {
    		kack = ARC;
    	}
    	printf("%.*Lf\n", 18, 100 * (x2 - x1 + y2 - y1) + best * (atan(1) * 20 - 20) + kack);
    //	cerr << "# " << tree.query(0, N).v << endl;
    }

Submission Info

Judge Result