Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <iomanip>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <cassert>
- #include <algorithm>
- #include <vector>
- #include <set>
- #include <utility>
- #include <cmath>
- #ifdef WIN32
- #define LLD "%I64d"
- #define LLU "%I64u"
- #else
- #define LLD "%lld"
- #define LLU "%llu"
- #endif
- using namespace std;
- #ifdef _DEBUG
- #define endline endl
- #else
- #define endline "\n"
- #endif
- #define pb push_back
- #define mp make_pair
- #define sz(a) (int(a.size()))
- #define itr(v) v::iterator
- typedef long long ll;
- typedef vector < int > vi;
- #define maxn 1200000
- typedef long double ans_t;
- struct List {
- List() : add_all(0LL), left(0), right(0), sum0(0LL), sum1(0LL), sum2(0LL) {}
- ans_t sum2, sum1, sum0;
- ll add_all;
- int left, right;
- ans_t getSum1() const {
- return (sum1 + add_all * sum0);
- }
- ans_t getSum2() const {
- return (sum2 + add_all * sum1 + (add_all) * (add_all - 1) / 2. * sum0);
- }
- ans_t getSum0() const {
- return sum0;
- }
- void upd(const List &a, const List &b) {
- sum2 = a.getSum2() + b.getSum2();
- sum1 = a.getSum1() + b.getSum1();
- sum0 = a.getSum0() + b.getSum0();
- add_all = 0;
- }
- bool isect(const int from, const int to) {
- return (max(left, from) < min(right, to));
- }
- };
- struct Tree
- {
- int curk;
- List sm[maxn];
- ans_t getAll() const {
- return sm[1].getSum2();
- }
- void upd(const int from, const int to, const int v, const int x) {
- if (sm[v].left >= from && sm[v].right <= to) {
- sm[v].add_all += x;
- } else {
- if (sm[v].isect(from, to)) {
- sm[2 * v].add_all += sm[v].add_all;
- sm[2 * v + 1].add_all += sm[v].add_all;
- upd(from, to, v * 2, x);
- upd(from, to, v * 2 + 1, x);
- sm[v].upd(sm[v * 2], sm[v * 2 + 1]);
- }
- }
- }
- };
- struct Event
- {
- int x, id, typ;
- int from, to;
- bool operator < (const Event &lhs) const {
- return (x < lhs.x || (x == lhs.x && typ < lhs.typ) || (x == lhs.x && typ == lhs.typ && id < lhs.id));
- }
- };
- int n, a, b;
- vi positions;
- vector < Event > sm;
- int cnt_pos;
- Tree tree;
- int main(void) {
- #ifdef NRISE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin >> n >> a >> b;
- positions.clear();
- sm.clear();
- for (int i = 0; i < n; ++i) {
- int cx, cy;
- cin >> cx >> cy;
- positions.push_back(cy);
- positions.push_back(cy + b);
- Event getEvent = {cx, i, 1, cy, cy + b};
- sm.push_back(getEvent);
- getEvent.x = cx + a; getEvent.typ = -1;
- sm.push_back(getEvent);
- }
- sort(sm.begin(), sm.end());
- sort(positions.begin(), positions.end());
- cnt_pos = unique(positions.begin(), positions.end()) - positions.begin();
- positions.resize(cnt_pos);
- --cnt_pos;
- ans_t ans = 0.0;
- tree.curk = 2;
- while (tree.curk < cnt_pos) {
- tree.curk *= 2;
- }
- for (int i = 0; i < cnt_pos; ++i) {
- tree.sm[i + tree.curk].left = positions[i];
- tree.sm[i + tree.curk].right = positions[i + 1];
- tree.sm[i + tree.curk].sum0 = positions[i + 1] - positions[i];
- tree.sm[i + tree.curk].add_all = 0LL;
- tree.sm[i + tree.curk].sum1 = 0.0;
- tree.sm[i + tree.curk].sum2 = 0.0;
- }
- for (int i = tree.curk - 1; i >= 1; --i) {
- tree.sm[i].upd(tree.sm[i * 2], tree.sm[i * 2 + 1]);
- tree.sm[i].left = tree.sm[2 * i].left;
- tree.sm[i].right = max(tree.sm[2 * i].right, tree.sm[2 * i + 1].right);
- }
- ans_t prev = 0.0;
- for (int i = 0; i < sz(sm); ++i) {
- ans += tree.getAll() * (sm[i].x - prev);
- prev = sm[i].x;
- tree.upd(sm[i].from, sm[i].to, 1, sm[i].typ);
- }
- cout << fixed << setprecision(20) << ans / (ans_t(n) * ans_t(n - 1) / 2.) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement