[题解] [JSOI2014] 矩形并

题面

题解

不想写了
嘿嘿嘿

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
", ans / n / (n - 1));
    return 0; 
}