Advertisement
Guest User

Untitled

a guest
Nov 17th, 2013
157
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.04 KB | None | 0 0
  1.             #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <cstring>
  7. #include <cassert>
  8. #include <algorithm>
  9. #include <vector>
  10. #include <set>
  11. #include <utility>
  12. #include <cmath>
  13.  
  14. #ifdef WIN32
  15. #define LLD "%I64d"
  16. #define LLU "%I64u"
  17. #else
  18. #define LLD "%lld"
  19. #define LLU "%llu"
  20. #endif
  21.  
  22. using namespace std;
  23.  
  24. #ifdef _DEBUG
  25. #define endline endl
  26. #else
  27. #define endline "\n"
  28. #endif
  29.  
  30. #define pb push_back
  31. #define mp make_pair
  32. #define sz(a) (int(a.size()))
  33. #define itr(v) v::iterator
  34.  
  35. typedef long long ll;
  36.  
  37. typedef vector < int > vi;
  38.  
  39. #define maxn 1200000
  40.  
  41. typedef long double ans_t;
  42.  
  43. struct List {
  44.     List() : add_all(0LL), left(0), right(0), sum0(0LL), sum1(0LL), sum2(0LL) {}
  45.     ans_t sum2, sum1, sum0;
  46.     ll add_all;
  47.     int left, right;
  48.     ans_t getSum1() const {
  49.         return (sum1 + add_all * sum0);
  50.     }
  51.     ans_t getSum2() const {
  52.         return (sum2 + add_all * sum1 + (add_all) * (add_all - 1) / 2. * sum0);
  53.     }
  54.     ans_t getSum0() const {
  55.         return sum0;
  56.     }
  57.     void upd(const List &a, const List &b) {
  58.         sum2 = a.getSum2() + b.getSum2();
  59.         sum1 = a.getSum1() + b.getSum1();
  60.         sum0 = a.getSum0() + b.getSum0();
  61.         add_all = 0;
  62.     }
  63.     bool isect(const int from, const int to) {
  64.         return (max(left, from) < min(right, to));
  65.     }
  66. };
  67.  
  68. struct Tree
  69. {
  70.     int curk;
  71.     List sm[maxn];
  72.     ans_t getAll() const {
  73.         return sm[1].getSum2();
  74.     }
  75.     void upd(const int from, const int to, const int v, const int x) {
  76.         if (sm[v].left >= from && sm[v].right <= to) {
  77.             sm[v].add_all += x;
  78.         } else {
  79.             if (sm[v].isect(from, to)) {
  80.                 sm[2 * v].add_all += sm[v].add_all;
  81.                 sm[2 * v + 1].add_all += sm[v].add_all;
  82.                 upd(from, to, v * 2, x);
  83.                 upd(from, to, v * 2 + 1, x);
  84.                 sm[v].upd(sm[v * 2], sm[v * 2 + 1]);
  85.             }
  86.         }
  87.     }
  88. };
  89.  
  90. struct Event
  91. {
  92.     int x, id, typ;
  93.     int from, to;
  94.  
  95.     bool operator < (const Event &lhs) const {
  96.         return (x < lhs.x || (x == lhs.x && typ < lhs.typ) || (x == lhs.x && typ == lhs.typ && id < lhs.id));
  97.     }
  98. };
  99.  
  100. int n, a, b;
  101. vi positions;
  102. vector < Event > sm;
  103. int cnt_pos;
  104. Tree tree;
  105.  
  106. int main(void) {
  107. #ifdef NRISE
  108.     freopen("input.txt", "r", stdin);
  109.     freopen("output.txt", "w", stdout);
  110. #endif
  111.     ios_base::sync_with_stdio(false);
  112.     cin >> n >> a >> b;
  113.     positions.clear();
  114.     sm.clear();
  115.     for (int i = 0; i < n; ++i) {
  116.         int cx, cy;
  117.         cin >> cx >> cy;
  118.         positions.push_back(cy);
  119.         positions.push_back(cy + b);
  120.         Event getEvent = {cx, i, 1, cy, cy + b};
  121.         sm.push_back(getEvent);
  122.         getEvent.x = cx + a; getEvent.typ = -1;
  123.         sm.push_back(getEvent);
  124.     }
  125.     sort(sm.begin(), sm.end());
  126.     sort(positions.begin(), positions.end());
  127.     cnt_pos = unique(positions.begin(), positions.end()) - positions.begin();
  128.     positions.resize(cnt_pos);
  129.     --cnt_pos;
  130.     ans_t ans = 0.0;
  131.     tree.curk = 2;
  132.     while (tree.curk < cnt_pos) {
  133.         tree.curk *= 2;
  134.     }
  135.     for (int i = 0; i < cnt_pos; ++i) {
  136.         tree.sm[i + tree.curk].left = positions[i];
  137.         tree.sm[i + tree.curk].right = positions[i + 1];
  138.         tree.sm[i + tree.curk].sum0 = positions[i + 1] - positions[i];
  139.         tree.sm[i + tree.curk].add_all = 0LL;
  140.         tree.sm[i + tree.curk].sum1 = 0.0;
  141.         tree.sm[i + tree.curk].sum2 = 0.0;
  142.     }
  143.     for (int i = tree.curk - 1; i >= 1; --i) {
  144.         tree.sm[i].upd(tree.sm[i * 2], tree.sm[i * 2 + 1]);
  145.         tree.sm[i].left = tree.sm[2 * i].left;
  146.         tree.sm[i].right = max(tree.sm[2 * i].right, tree.sm[2 * i + 1].right);
  147.     }
  148.     ans_t prev = 0.0;
  149.     for (int i = 0; i < sz(sm); ++i) {
  150.         ans += tree.getAll() * (sm[i].x - prev);
  151.         prev = sm[i].x;
  152.         tree.upd(sm[i].from, sm[i].to, 1, sm[i].typ);
  153.     }
  154.     cout << fixed << setprecision(20) << ans / (ans_t(n) * ans_t(n - 1) / 2.) << endl;
  155.     return 0;
  156. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement