题面
题解
不想写了
嘿嘿嘿 http://m-sea-blog.com/archives/4658/
- Code
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdio>
- typedef long double ll;
- const int lim = 2e6 + 5;
- const int N = 2e5 + 5;
- using namespace std;
- int n, cnt;
- struct node
- {
- int opt, x, l, r, v;
- node(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0)
- {
- opt = a, x = b, l = c, r = d, v = e;
- }
- bool operator <(const node &p) const
- {
- return x == p.x ? (opt == p.opt ? v < p.v : opt < p.opt) : x < p.x;
- }
- } q[N << 2];
- struct Tree
- {
- ll t[lim];
- void add(int x, ll y) { for(int i = x; i < lim; i += (i & -i)) t[i] += y; }
- ll query(int x) { ll res = 0; for(int i = x; i> 0; i -= (i & -i)) res += t[i]; return res; }
- } A, B, C, D;
- ll ans;
- template <typename T>
- inline T read()
- {
- T x = 0, w = 1; char c = getchar();
- while(c <'0' || c> '9') { if(c == '-') w = -1; c = getchar(); }
- while(c>= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
- return x * w;
- }
- void modify(int x, int y, int v)
- {
- A.add(y, v), B.add(y, x * v), C.add(y, y * v), D.add(y, (ll) x * y * v);
- }
- ll query(int x, int y)
- {
- return A.query(y) * (x + 1) * (y + 1) - B.query(y) * (y + 1) - C.query(y) * (x + 1) + D.query(y);
- }
- int main()
- {
- n = read <int> ();
- for(int x, y, a, b, i = 1; i <= n; i++)
- {
- x = read <int> () + 2, y = read <int> () + 2, a = read <int> (), b = read <int> ();
- q[++cnt] = node(0, y, x, x + a - 1, 1), q[++cnt] = node(0, y + b, x, x + a - 1, -1);
- q[++cnt] = node(1, y - 1, x, x + a - 1, -1), q[++cnt] = node(1, y + b - 1, x, x + a - 1, 1);
- ans -= 1ll * a * b;
- }
- sort(q + 1, q + cnt + 1);
- for(int i = 1; i <= cnt; i++)
- {
- if(q[i].opt)
- ans += q[i].v * (query(q[i].x, q[i].r) - query(q[i].x, q[i].l - 1));
- else modify(q[i].x, q[i].l, q[i].v), modify(q[i].x, q[i].r + 1, -q[i].v);
- }
- printf("%.9Lf\n", ans / n / (n - 1));
- return 0;
- }
[题解] [JSOI2014] 矩形并
来源: http://www.bubuko.com/infodetail-3416741.html