题解 P1756 【[NOI2009]描边】

弓虽太弱 · 2019-07-12 20:10:12 · 题解

#pragma GCC optimize(2)
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define sqr(x) ((x) * (x))
typedef long double LLF;
static const LLF PI = 3.14159265358979324L,
             zero = 1e-18L, INF = 1e1729L;
static const int maxN = 5010;
struct vec
{
    LLF x, y; vec() {} vec(LLF x, LLF y): x(x), y(y) {}
    vec operator+(const vec &b) const {return vec(x + b.x, y + b.y);}
    vec operator-(const vec &b) const {return vec(x - b.x, y - b.y);}
    vec operator*(const LLF &t) const {return vec(x * t, y * t);}
    vec operator/(const LLF &t) const {return vec(x / t, y / t);}
} p[maxN];
struct Rec {vec a, b, c, d;} rec[maxN];
struct Seg
{
    LLF L, R; Seg() {} Seg(LLF L, LLF R): L(L), R(R) {}
    bool operator<(const Seg &b) const {return L < b.L;}
} seg[maxN];
int a[maxN], b[maxN], n, m; LLF r; bool marked[maxN];

LLF abs(const vec &p) {return sqrt(p.x * p.x + p.y * p.y);}
void update(LLF &L, LLF &R, LLF x) {if (x < L) L = x; if (x > R) R = x;}
void testcross(LLF x, LLF &L, LLF &R, vec A, vec B)
{
    if ((x - A.x > -zero && x - B.x < zero) ||
        (x - B.x > -zero && x - A.x < zero))
        update(L, R, (B.y - A.y) / (B.x - A.x) * (x - A.x) + A.y);
    return;
}
LLF f(LLF x)
{
    static Seg seg[maxN]; int cnt = 0;
    for (int i = 0; i < n; ++i) if (fabs(p[i].x - x) < r)
    {
        LLF dist = sqrt(sqr(r) - sqr(p[i].x - x));
        seg[cnt++] = Seg(p[i].y - dist, p[i].y + dist);
    }
    for (int i = 0; i < m; ++i)
    {
        LLF L = INF, R = -INF;
        testcross(x, L, R, rec[i].a, rec[i].b);
        testcross(x, L, R, rec[i].b, rec[i].c);
        testcross(x, L, R, rec[i].c, rec[i].d);
        testcross(x, L, R, rec[i].d, rec[i].a);
        if (L < INF && R > -INF) seg[cnt++] = Seg(L, R);
    }
    if (!cnt) return 0;
    std::sort(seg, seg + cnt);
    LLF L = seg[0].L, R = seg[0].R, len = 0;
    for (int i = 1; i < cnt; ++i)
    if (R < seg[i].L) len += R - L,
        L = seg[i].L, R = seg[i].R;
    else if (R < seg[i].R) R = seg[i].R;
    return len += R - L;
}
LLF area(LLF L, LLF R, LLF fL, LLF fMid, LLF fR)
{return (R - L) * (fL + 4 * fMid + fR) / 6;}
LLF calc(LLF L, LLF Mid, LLF R, LLF fL, LLF fMid, LLF fR, LLF pre)
{
    LLF Mid_L = (L + Mid) / 2, Mid_R = (Mid + R) / 2,
        fMid_L = f(Mid_L), fMid_R = f(Mid_R),
        SL = area(L, Mid, fL, fMid_L, fMid),
        SR = area(Mid, R, fMid, fMid_R, fR);
    if (fabs(SL + SR - pre) < zero) return SL + SR;
    else return calc(L, Mid_L, Mid, fL, fMid_L, fMid, SL) +
                calc(Mid, Mid_R, R, fMid, fMid_R, fR, SR);
}
LLF get_area(LLF L, LLF R)
{
    LLF Mid = (L + R) / 2, fL = f(L), fMid = f(Mid), fR = f(R),
        pre = area(L, R, fL, fMid, fR);
    return calc(L, Mid, R, fL, fMid, fR, pre);
}

int main()
{
    srand(time(NULL)); scanf("%d", &n);
    LLF theta = (LLF) rand() / RAND_MAX * 2 * PI,
        dx = (LLF) rand() / RAND_MAX * 1e3,
        dy = (LLF) rand() / RAND_MAX * 1e3;
    for (int i = 0; i < n; ++i)
    {
        LLF x, y; scanf("%Lf%Lf", &x, &y); x += dx, y += dy;
        p[i] = vec(cos(theta) * x - sin(theta) * y,
                    cos(theta) * y + sin(theta) * x);
    }
    scanf("%d", &m);
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d", a + i, b + i);
        marked[--a[i]] = marked[--b[i]] = 1;
    }
    scanf("%Lf", &r);
    for (int i = 0; i < m; ++i)
    {
        int u = a[i], v = b[i]; vec tmp(p[u] - p[v]);
        LLF dist = abs(tmp),
            dx = tmp.y * r / dist,
            dy = -tmp.x * r / dist;
        vec dir(dx, dy);
        rec[i].a = p[u] - dir; rec[i].b = p[v] - dir;
        rec[i].c = p[v] + dir; rec[i].d = p[u] + dir;
    }
    int cnt = 0;
    for (int i = 0; i < n; ++i) if (marked[i]) p[cnt++] = p[i];
    n = cnt; cnt = 0;
    for (int i = 0; i < n; ++i)
        seg[cnt++] = Seg(p[i].x - r, p[i].x + r);
    for (int i = 0; i < m; ++i)
    {
        LLF L = INF, R = -INF;
        update(L, R, rec[i].a.x);
        update(L, R, rec[i].b.x);
        update(L, R, rec[i].c.x);
        update(L, R, rec[i].d.x);
        if (L < INF && R > -INF) seg[cnt++] = Seg(L, R);
    }
    std::sort(seg, seg + cnt);
    LLF L = seg[0].L, R = seg[0].R, S = 0;
    for (int i = 1; i < cnt; ++i)
    if (R < seg[i].L) S += get_area(L, R),
        L = seg[i].L, R = seg[i].R;
    else if (R < seg[i].R) R = seg[i].R;
    printf("%.18Lf\n", S += get_area(L, R));
    return 0;
}