Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <vector>
- #include <string>
- #include <set>
- #include <map>
- #include <cmath>
- #include <cstdlib>
- #include <cstring>
- #include <algorithm>
- #include <cassert>
- using namespace std;
- template <class T> T sqr(T x) { return x*x; }
- const int INF = 1000*1000*1000;
- const long long INF64 = sqr(static_cast<long long>(INF));
- const double PI = acos(-1.0);
- const int N = 2000*1010;
- const int MAXN = 200200;
- const int K = 2*N+N/5;
- typedef __int128_t ll;
- ll tsum2[K];
- long long tsum[K];
- int lz[K];
- int n, a, b;
- void push(int t, int tl, int tr)
- {
- ll d = lz[t];
- lz[t] = 0;
- if (tl != tr)
- {
- lz[2*t] += d;
- lz[2*t+1] += d;
- }
- tsum2[t] += d * tsum[t] + d * (d - 1) / 2 * (tr - tl + 1);
- tsum[t] += (tr-tl+1) * d;
- }
- inline void inc(int l, int r, ll d, int t, int tl, int tr)
- {
- push(t, tl, tr);
- if (tl == l && tr == r)
- {
- lz[t] += d;
- push(t, tl, tr);
- return;
- }
- int tm = (tl+tr)/2;
- if (r <= tm)
- inc(l, r, d, 2*t, tl, tm);
- else if (l > tm)
- inc(l, r, d, 2*t+1, tm+1, tr);
- else {
- inc(l, tm, d, 2*t, tl, tm);
- inc(tm+1, r, d, 2*t+1, tm+1, tr);
- }
- push(2 * t, tl, tm);
- push(2 * t + 1, tm + 1, tr);
- tsum[t] = tsum[2*t] + tsum[2*t+1];
- tsum2[t] = tsum2[2*t] + tsum2[2*t+1];
- }
- inline ll get(int l, int r, int t, int tl, int tr)
- {
- push(t, tl, tr);
- if (tl == l && tr == r)
- return tsum2[t];
- int tm = (tl+tr)/2;
- if (r <= tm)
- return get(l, r, 2*t, tl, tm);
- if (l > tm)
- return get(l, r, 2*t+1, tm+1, tr);
- return get(l, tm, 2*t, tl, tm) + get(tm+1, r, 2*t+1, tm+1, tr);
- }
- inline void inc(int l, int r, int d)
- {
- inc(l, r, d, 1, 0, N-1);
- }
- inline ll get(int l, int r)
- {
- return get(l, r, 1, 0, N-1);
- }
- struct evt
- {
- int x, y;
- bool st;
- evt()
- { }
- evt(int x, int y, bool st) : x(x), y(y), st(st)
- { }
- } q[2 * MAXN];
- bool operator <(const evt &a, const evt &b)
- {
- return a.x < b.x;
- }
- int main()
- {
- cerr << (sizeof(tsum2) + sizeof(tsum) + sizeof(lz) + sizeof(q)) / 1024 / 1024 << endl;
- cin >> n >> a >> b;
- // a = b = n = 1000*1000;
- for (int i = 0; i < n; ++i)
- {
- int x, y;
- scanf("%d%d", &x, &y);
- // x = rand() % 1000000;
- // y = rand() % 1000000;
- q[i << 1] = evt(x, y, true);
- q[(i << 1) | 1] = evt(x + a, y, false);
- }
- sort(q, q + 2 * n);
- ll ans = 0;
- for (int x = 0, i = 0; x < N; ++x)
- {
- while (i < 2 * n && q[i].x == x)
- {
- inc(q[i].y, q[i].y + b - 1, q[i].st ? 1 : -1);
- ++i;
- }
- ans += get(0, N-1);
- }
- printf("%.10lf\n", (double)(1.0 * ans / (1LL * n * (n - 1) / 2)));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement