2021-team4-paste

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int n, x[100005], y[100005], r[100005], v[100005];
set<pii> cirSet;
struct ifo {
    int x, i, ty;
    friend bool operator < (const ifo &a, const ifo &b) {
        if (a.x != b.x)
            return a.x < b.x;
        if (a.ty != b.ty)
            return a.ty < b.ty;
        if (r[a.i] != r[b.i])
            return r[a.i] < r[b.i];
        return a.i < b.i; 
    }
};
int main() {
    freopen("circles.in", "r", stdin);
    freopen("circles.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++)
        scanf("%d%d%d", x + i, y + i, r + i);
    vector<ifo> vec;
    for (int i = 1; i <= n; i ++) {
        vec.push_back((ifo){x[i] - r[i], i, +1});
        vec.push_back((ifo){x[i] + r[i], i, -1});
    }
    sort(vec.begin(), vec.end());
    double ans = 0;
    for (auto it : vec) {
        int i = it.i;
        if (++ v[i] == 2) {
            if (cirSet.count(pii(y[i], i))) {
                static const double PI = acos(-1);
                ans += PI * r[i] * r[i];
                cirSet.erase(pii(y[i], i));
            }
        }
        else {
            static const pii emp(-1, -1);
            auto getPre = [&](int y) {
                auto v = cirSet.upper_bound(pii(y, n));
                if (v == cirSet.begin())
                    return emp;
                return *--v;
            };
            auto getNxt = [&](int y) {
                auto v = cirSet.upper_bound(pii(y, n));
                if (v == cirSet.end())
                    return emp;
                return *v;
            };
            auto contain = [&](int i, int j) {
                return r[i] >= r[j] && 1ll * (r[i] - r[j]) * (r[i] - r[j]) >= 
                    1ll * (x[i] - x[j]) * (x[i] - x[j]) + 1ll * (y[i] - y[j]) * (y[i] - y[j]);
            };
            auto pre = getPre(y[i]);
            if (pre != emp && contain(pre.second, i))
                continue;
            auto nxt = getNxt(y[i]);
            if (nxt != emp && contain(nxt.second, i))
                continue;
            while (1) {
                auto pre = getPre(y[i]);
                if (pre == emp)
                    break;
                if (contain(i, pre.second))
                    cirSet.erase(pre);
                else
                    break;
            }
            while (1) {
                auto nxt = getNxt(y[i]);
                if (nxt == emp)
                    break;
                if (contain(i, nxt.second))
                    cirSet.erase(nxt);
                else
                    break;
            }
            cirSet.insert(pii(y[i], i));
        }
    }
    printf("%.20lf\n", ans);
    return 0;
}

#include

using namespace std;

using pii = pair;

int n, x[100005], y[100005], r[100005], v[100005];

set cirSet;

struct ifo {

int x, i, ty;

friend bool operator < (const ifo &a, const ifo &b) {

if (a.x != b.x)

return a.x < b.x;

if (a.ty != b.ty)

return a.ty < b.ty;

if (r[a.i] != r[b.i])

return r[a.i] < r[b.i];

return a.i < b.i;

}

};

int main() {

freopen("circles.in", "r", stdin);

freopen("circles.out", "w", stdout);

scanf("%d", &n);

for (int i = 1; i <= n; i ++)

scanf("%d%d%d", x + i, y + i, r + i);

vector vec;

for (int i = 1; i <= n; i ++) {

vec.push_back((ifo){x[i] - r[i], i, +1});

vec.push_back((ifo){x[i] + r[i], i, -1});

}

sort(vec.begin(), vec.end());

double ans = 0;

for (auto it : vec) {

int i = it.i;

if (++ v[i] == 2) {

if (cirSet.count(pii(y[i], i))) {

static const double PI = acos(-1);

ans += PI * r[i] * r[i];

cirSet.erase(pii(y[i], i));

}

}

else {

static const pii emp(-1, -1);

auto getPre = [&](int y) {

auto v = cirSet.upper_bound(pii(y, n));

if (v == cirSet.begin())

return emp;

return *--v;

};

auto getNxt = [&](int y) {

auto v = cirSet.upper_bound(pii(y, n));

if (v == cirSet.end())

return emp;

return *v;

};

auto contain = [&](int i, int j) {

return r[i] >= r[j] && 1ll * (r[i] - r[j]) * (r[i] - r[j]) >=

1ll * (x[i] - x[j]) * (x[i] - x[j]) + 1ll * (y[i] - y[j]) * (y[i] - y[j]);

};

auto pre = getPre(y[i]);

if (pre != emp && contain(pre.second, i))

continue;

auto nxt = getNxt(y[i]);

if (nxt != emp && contain(nxt.second, i))

continue;

while (1) {

auto pre = getPre(y[i]);

if (pre == emp)

break;

if (contain(i, pre.second))

cirSet.erase(pre);

else

break;

}

while (1) {

auto nxt = getNxt(y[i]);

if (nxt == emp)

break;

if (contain(i, nxt.second))

cirSet.erase(nxt);

else

break;

}

cirSet.insert(pii(y[i], i));

}

}

printf("%.20lf\n", ans);

return 0;

}

附加文件