Description

在平面直角坐标系中给定 \(n\) 个圆. 已知这些圆两两没有交点, 即两圆的关系只存在相离和 包含. 求这些圆的异或面积并. 异或面积并为: 当一片区域在奇数个圆内则计算其面积, 当一片区域在偶数个圆内则不考虑.

Input

第一行包含一个正整数 \(n\), 代表圆的个数. 接下来 \(n\) 行, 每行 \(3\) 个非负整数 \(x, y, r\), 表示一个圆心在 \((x, y)\), 半径为 \(r\) 的圆.

Output

仅一行一个整数, 表示所有圆的异或面积并除以圆周率 Pi 的结果.

Sample Input

2
0 0 1
0 0 2

Sample Output

3

Data Range

对于所有数据, 保证 \(|x|, |y| \leq 10^8, r \gt 0, n \leq 200000\)

Explanation

首先好不容易写好的一道题拍了半天还是没有拍对实在是郁闷 QwQ

然后花了三四个小时调完了才发现是这么一个傻逼 (对于粗口我很抱歉, 但是这种低级错误 我实在不能忍) 错误:

res += (long long)(R[e[i].id]) * R[e[i].id]; // Correct
res += (long long)(R[e[i].id] * R[e[i].id]); // FIXME: Incorrect!!!!!

能犯这种奇葩的问题我也是没谁了...... 23333333333333333

这正应验了 @huangsi 大神曾说过的一句话:

不开 long long 见祖宗, 十年 OI 一场空!

我觉得这句话可以奉为我的座右铭了 QwQ

好了说正事==这题用扫描线做法, 然后简单在 set 上面瞎搞一发就可以了...... 只要 你注意精度问题, 其实基本没什么事......

原文链接:http://blog.csdn.net/neither_nor/article/details/51386526

首先可知一个圆被奇数个圆套则答案减去其面积, 被偶数个套则加上其面积, 然后我们维护一个垂直于 x 轴扫描线, 从左向右扫, 每个圆拆成加入和删除两个事件, 由于圆和圆不相交, 所以一个圆可以看成一个括号, 整个扫描线上是一个括号序列, 而且随扫描线当前 x 增加括号之间相对顺序不变 (扫描线都是某些相对顺序不变, 然后维护当前 x?)

因为圆和圆不相交, 所以加入和删除的时候肯定都是对最内层的括号操作, 只会影响到自己, 所以我们只需要对扫描线上每个点记录他属于哪个圆 (算出当前 x 下 y 坐标), 是左括号还是右括号和外边套了几层 (在新加入括号的时候用这两个算出新加的括号是第几层), 然后在加入一对括号的时候查询他外面套了几层更新答案即可

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>

#define sqr(__x) (1.0*(__x)*(__x))
using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 400100;
const lli infinit = 1000000000;
const llf epsilon = 1e-8;

int n, ecnt;
int X[maxn], Y[maxn], R[maxn];
llf curx;

struct srtr {
    int loc, id;
} e[maxn];
bool operator < (srtr a, srtr b) {
    return a.loc < b.loc; }

struct circle {
    bool above;
    int id, cnt;
    circle(bool _, int __, int ___ = 0) {
        above = _, id = __, cnt = ___;
        return ; }
    llf y(llf x) {
        llf tmp = sqrt(sqr(R[id]) - sqr(x - X[id]));
        if (!above) tmp = -tmp;
        return Y[id] + tmp;
    }
};
bool operator < (circle a, circle b) {
    llf ay = a.y(curx), by = b.y(curx);
    if (fabs(ay - by) > epsilon)
        return ay > by;
    return a.above > b.above;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &X[i], &Y[i], &R[i]);
        e[++ecnt].loc = X[i] - R[i];
        e[ecnt].id = i;
        e[++ecnt].loc = X[i] + R[i];
        e[ecnt].id = -i;
    }
    sort(e + 1, e + 1 + ecnt);
    // Begin sorting the stuff
    set<circle> st;
    R[0] = infinit;
    curx = -infinit;
    st.insert(circle(true, 0, -1));
    st.insert(circle(false, 0, -1));
    int cnt = -1;
    lli res = 0;
    for (int i = 1; i <= ecnt; i++) {
        curx = e[i].loc;
        if (e[i].id > 0) {
            circle t = *st.upper_bound(circle(false, e[i].id));
            cnt = t.cnt + (t.above ? 0 : 1);
            res += (lli)(R[e[i].id]) * R[e[i].id] * ((cnt & 1) ? -1 : 1);
            st.insert(circle(true, e[i].id, cnt));
            st.insert(circle(false, e[i].id, cnt));
        } else {
            e[i].id = -e[i].id;
            st.erase(circle(true, e[i].id, cnt));
            st.erase(circle(false, e[i].id, cnt));
        }
    }
    // Output result
    printf("%lld\n", res);
    return 0;
}