Advertisement
Guest User

Untitled

a guest
Nov 17th, 2013
156
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.56 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <iomanip>
  6. #include <string>
  7. #include <cassert>
  8. #include <vector>
  9. #include <cstring>
  10. #include <queue>
  11. using namespace std;
  12.  
  13. #define mp make_pair
  14. #define pb push_back
  15. #define all(v) (v).begin(), (v).end()
  16. #define sz(v) (int)(v).size()
  17. typedef long long LL;
  18. typedef long double LD;
  19.  
  20. const int N = 2000007;
  21. LL s[4200007], add[4200007];
  22. LD f[4200007];
  23. struct segtree
  24. {
  25.     inline LL gets(int v, int tl, int tr)
  26.     {
  27.         return s[v] + (tr - tl + 1) * add[v];
  28.     }
  29.  
  30.     inline LD getf(int v, int tl, int tr)
  31.     {
  32.         LL k = add[v];
  33.         if (k == 0) return f[v];
  34.         if (k < 0)
  35.         {
  36.             k = -k;
  37.             LD ret = f[v];
  38.             ret -= gets(v, tl, tr) * k;
  39.             ret -= (tr - tl + 1) * (LD)k * (k - 1) / 2.0;
  40.             return ret;
  41.         }
  42.         LD ret = f[v];
  43.         ret += s[v] * k;
  44.         ret += (tr - tl + 1) * (LD)k * (k - 1) / 2.0;
  45.         return ret;
  46.     }
  47.  
  48.     void push(int v, int tl, int tr)
  49.     {
  50.         add[2 * v] += add[v];
  51.         add[2 * v + 1] += add[v];
  52.         f[v] = getf(v, tl, tr);
  53.         s[v] = gets(v, tl, tr);
  54.         add[v] = 0;
  55.     }
  56.  
  57.     void update(int v, int tl, int tr, int l, int r, int d)
  58.     {
  59.         if (tl == l && tr == r)
  60.         {
  61.             add[v] += d;
  62.             return;
  63.         }
  64.         push(v, tl, tr);
  65.         int tm = (tl + tr) / 2;
  66.         if (r <= tm) update(2*v, tl, tm, l, r, d);
  67.         else if (l > tm) update(2*v+1, tm+1, tr, l, r, d);
  68.         else
  69.         {
  70.             update(2*v, tl, tm, l, tm, d);
  71.             update(2*v+1, tm+1, tr, tm+1, r, d);
  72.         }
  73.         s[v] = gets(2*v, tl, tm) + gets(2*v+1, tm+1,tr);
  74.         f[v] = getf(2*v, tl, tm) + getf(2*v+1, tm+1, tr);
  75.     }
  76.  
  77.     LD F()
  78.     {
  79.         return getf(1, 0, N - 1);
  80.     }
  81.  
  82. } tree;
  83.  
  84. vector<int> X[N/2];
  85. int n, a, b;
  86.  
  87. inline void addPt(int y)
  88. {
  89.     tree.update(1, 0, N - 1, y, y + b - 1, +1);
  90. }
  91.  
  92. inline void erase(int y)
  93. {
  94.     tree.update(1, 0, N - 1, y, y + b - 1, -1);
  95. }
  96.  
  97. int main()
  98. {
  99.     //freopen("input.txt","r",stdin);
  100.     //freopen("output.txt","w",stdout);
  101.  
  102.    
  103.     scanf("%d%d%d", &n, &a, &b);
  104.     for(int i = 0; i < n; ++i)
  105.     {
  106.         int x, y;
  107.         scanf("%d%d", &x, &y);
  108.         X[x].pb(y);
  109.     }
  110.     /*
  111.     n = 200000;
  112.     a = 1000000;
  113.     b = 1000000;
  114.     for(int i = 0; i < n; ++i)
  115.     {
  116.         int x = (rand() * rand() + rand()) % a;
  117.         int y = (rand() * rand() + rand()) % a;
  118.         X[x].pb(y);
  119.     }
  120.     */
  121.     for(int i = 0; i < sz(X[0]); ++i) addPt(X[0][i]);
  122.     LD ans = 0.0;
  123.     for(int pos = 1; pos < N; ++pos)
  124.     {
  125.         ans += tree.F();
  126.         if (pos < N / 2) for(int i = 0; i < sz(X[pos]); ++i) addPt(X[pos][i]);
  127.         if (pos >= a && pos - a < N / 2) for(int i = 0; i < sz(X[pos - a]); ++i) erase(X[pos-a][i]);
  128.     }
  129.     cout << fixed << setprecision(9) << ans / (LD)n / (n - 1) * 2.0 << endl;
  130.  
  131.     return 0;
  132. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement