Advertisement
Guest User

Untitled

a guest
Nov 18th, 2013
168
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.85 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <vector>
  4. #include <string>
  5. #include <set>
  6. #include <map>
  7. #include <cmath>
  8. #include <cstdlib>
  9. #include <cstring>
  10. #include <algorithm>
  11. #include <cassert>
  12.  
  13. using namespace std;
  14.  
  15. template <class T> T sqr(T x) { return x*x; }
  16.  
  17. const int INF = 1000*1000*1000;
  18. const long long INF64 = sqr(static_cast<long long>(INF));
  19. const double PI = acos(-1.0);
  20.  
  21. const int N = 2000*1010;
  22. const int MAXN = 200200;
  23. const int K = 2*N+N/5;
  24.  
  25. typedef __int128_t ll;
  26.  
  27. ll tsum2[K];
  28. long long tsum[K];
  29. int lz[K];
  30. int n, a, b;
  31.  
  32. void push(int t, int tl, int tr)
  33. {
  34.     ll d = lz[t];
  35.  
  36.     lz[t] = 0;
  37.     if (tl != tr)
  38.     {
  39.         lz[2*t] += d;
  40.         lz[2*t+1] += d;
  41.     }
  42.  
  43.     tsum2[t] += d * tsum[t] + d * (d - 1) / 2 * (tr - tl + 1);
  44.     tsum[t] += (tr-tl+1) * d;
  45. }
  46.  
  47. inline void inc(int l, int r, ll d, int t, int tl, int tr)
  48. {
  49.     push(t, tl, tr);
  50.     if (tl == l && tr == r)
  51.     {
  52.         lz[t] += d;
  53.         push(t, tl, tr);
  54.         return;
  55.     }
  56.     int tm = (tl+tr)/2;
  57.     if (r <= tm)
  58.         inc(l, r, d, 2*t, tl, tm);
  59.     else if (l > tm)
  60.         inc(l, r, d, 2*t+1, tm+1, tr);
  61.     else {
  62.         inc(l, tm, d, 2*t, tl, tm);
  63.         inc(tm+1, r, d, 2*t+1, tm+1, tr);
  64.     }
  65.     push(2 * t, tl, tm);
  66.     push(2 * t + 1, tm + 1, tr);
  67.     tsum[t] = tsum[2*t] + tsum[2*t+1];
  68.     tsum2[t] = tsum2[2*t] + tsum2[2*t+1];
  69. }
  70.  
  71. inline ll get(int l, int r, int t, int tl, int tr)
  72. {
  73.     push(t, tl, tr);
  74.     if (tl == l && tr == r)
  75.         return tsum2[t];
  76.     int tm = (tl+tr)/2;
  77.     if (r <= tm)
  78.         return get(l, r, 2*t, tl, tm);
  79.     if (l > tm)
  80.         return get(l, r, 2*t+1, tm+1, tr);
  81.     return get(l, tm, 2*t, tl, tm) + get(tm+1, r, 2*t+1, tm+1, tr);
  82. }
  83.  
  84. inline void inc(int l, int r, int d)
  85. {
  86.     inc(l, r, d, 1, 0, N-1);
  87. }
  88.  
  89. inline ll get(int l, int r)
  90. {
  91.     return get(l, r, 1, 0, N-1);
  92. }
  93.  
  94. struct evt
  95. {
  96.     int x, y;
  97.     bool st;
  98.  
  99.     evt()
  100.     { }
  101.  
  102.     evt(int x, int y, bool st) : x(x), y(y), st(st)
  103.     { }
  104. } q[2 * MAXN];
  105.  
  106. bool operator <(const evt &a, const evt &b)
  107. {
  108.     return a.x < b.x;
  109. }
  110.  
  111. int main()
  112. {
  113.     cerr << (sizeof(tsum2) + sizeof(tsum) + sizeof(lz) + sizeof(q)) / 1024 / 1024 << endl;
  114.     cin >> n >> a >> b;
  115.  
  116.     // a = b = n = 1000*1000;
  117.  
  118.     for (int i = 0; i < n; ++i)
  119.     {
  120.         int x, y;
  121.         scanf("%d%d", &x, &y);
  122.         // x = rand() % 1000000;
  123.         // y = rand() % 1000000;
  124.         q[i << 1] = evt(x, y, true);
  125.         q[(i << 1) | 1] = evt(x + a, y, false);
  126.     }
  127.     sort(q, q + 2 * n);
  128.  
  129.     ll ans = 0;
  130.     for (int x = 0, i = 0; x < N; ++x)
  131.     {
  132.         while (i < 2 * n && q[i].x == x)
  133.         {
  134.             inc(q[i].y, q[i].y + b - 1, q[i].st ? 1 : -1);
  135.             ++i;
  136.         }
  137.         ans += get(0, N-1);
  138.     }
  139.  
  140.     printf("%.10lf\n", (double)(1.0 * ans / (1LL * n * (n - 1) / 2)));
  141.  
  142.     return 0;
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement