Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <iostream>
- #include <algorithm>
- #include <iomanip>
- #include <string>
- #include <cassert>
- #include <vector>
- #include <cstring>
- #include <queue>
- using namespace std;
- #define mp make_pair
- #define pb push_back
- #define all(v) (v).begin(), (v).end()
- #define sz(v) (int)(v).size()
- typedef long long LL;
- typedef long double LD;
- const int N = 2000007;
- LL s[4200007], add[4200007];
- LD f[4200007];
- struct segtree
- {
- inline LL gets(int v, int tl, int tr)
- {
- return s[v] + (tr - tl + 1) * add[v];
- }
- inline LD getf(int v, int tl, int tr)
- {
- LL k = add[v];
- if (k == 0) return f[v];
- if (k < 0)
- {
- k = -k;
- LD ret = f[v];
- ret -= gets(v, tl, tr) * k;
- ret -= (tr - tl + 1) * (LD)k * (k - 1) / 2.0;
- return ret;
- }
- LD ret = f[v];
- ret += s[v] * k;
- ret += (tr - tl + 1) * (LD)k * (k - 1) / 2.0;
- return ret;
- }
- void push(int v, int tl, int tr)
- {
- add[2 * v] += add[v];
- add[2 * v + 1] += add[v];
- f[v] = getf(v, tl, tr);
- s[v] = gets(v, tl, tr);
- add[v] = 0;
- }
- void update(int v, int tl, int tr, int l, int r, int d)
- {
- if (tl == l && tr == r)
- {
- add[v] += d;
- return;
- }
- push(v, tl, tr);
- int tm = (tl + tr) / 2;
- if (r <= tm) update(2*v, tl, tm, l, r, d);
- else if (l > tm) update(2*v+1, tm+1, tr, l, r, d);
- else
- {
- update(2*v, tl, tm, l, tm, d);
- update(2*v+1, tm+1, tr, tm+1, r, d);
- }
- s[v] = gets(2*v, tl, tm) + gets(2*v+1, tm+1,tr);
- f[v] = getf(2*v, tl, tm) + getf(2*v+1, tm+1, tr);
- }
- LD F()
- {
- return getf(1, 0, N - 1);
- }
- } tree;
- vector<int> X[N/2];
- int n, a, b;
- inline void addPt(int y)
- {
- tree.update(1, 0, N - 1, y, y + b - 1, +1);
- }
- inline void erase(int y)
- {
- tree.update(1, 0, N - 1, y, y + b - 1, -1);
- }
- int main()
- {
- //freopen("input.txt","r",stdin);
- //freopen("output.txt","w",stdout);
- scanf("%d%d%d", &n, &a, &b);
- for(int i = 0; i < n; ++i)
- {
- int x, y;
- scanf("%d%d", &x, &y);
- X[x].pb(y);
- }
- /*
- n = 200000;
- a = 1000000;
- b = 1000000;
- for(int i = 0; i < n; ++i)
- {
- int x = (rand() * rand() + rand()) % a;
- int y = (rand() * rand() + rand()) % a;
- X[x].pb(y);
- }
- */
- for(int i = 0; i < sz(X[0]); ++i) addPt(X[0][i]);
- LD ans = 0.0;
- for(int pos = 1; pos < N; ++pos)
- {
- ans += tree.F();
- if (pos < N / 2) for(int i = 0; i < sz(X[pos]); ++i) addPt(X[pos][i]);
- if (pos >= a && pos - a < N / 2) for(int i = 0; i < sz(X[pos - a]); ++i) erase(X[pos-a][i]);
- }
- cout << fixed << setprecision(9) << ans / (LD)n / (n - 1) * 2.0 << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement