[bzoj 4561] [JLoi2016]圆的异或并

给出两两没有交点的n个圆(x,y,r), 求被圆面覆盖奇数次的区域的总面积. 输出面积除以pi的结果. (|x|,|y|≤10^8, r>0, n≤2*10^5) 把圆拆成上半弧和下半弧, 扫描线, 用set维护. 两个圆之间的相对关系是不会变化的, 所以代入求值比较纵坐标即可.

下面的代码可以写得更简洁. 我把同一个圆上半弧和下半弧的事件也拆开了. 事实上没有必要. 如果不拆, 排序只比较端点就可以了.

看到有一些代码用圆的编号的正负来区别插入和删除, 感觉不错......

typedef long long ll;

const int N = 2e5;
const long double eps = 1e-9;

ll x0;
int cnt1, cnt2;
bool d[N];

struct Arc
{
	ll x, y, r;
	short t;
	long double y0()
	{
		return y + t * sqrt((long double)(r*r - (x0-x) * (x0-x)));
	}
} A[2*N];

struct Event
{
	short t; // t=-1, open; t=1, close
	int k;
	
	bool operator<(const Event& o) const
	{
		ll x1 = A[k].x + t * A[k].r, x2 = A[o.k].x + o.t * A[o.k].r;
		return x1 < x2 || (x1 == x2 && A[k].y < A[o.k].y)
			|| (x1 == x2 && A[k].y == A[o.k].y && A[k].t < A[o.k].t);
	}
} E[4*N];

struct Cmp
{
	bool operator()(int i, int j) const
	{
		long double y1 = A[i].y0(), y2 = A[j].y0(), dy = fabs(y1-y2);
		return (y1 < y2 && dy >= eps) || (dy < eps && A[i].t < A[j].t);
	}
};

set<int, Cmp> S;

inline void add(ll x, ll y, ll r, short t)
{
	A[cnt1] = (Arc){x, y, r, t};
	E[cnt2++] = (Event){1, cnt1};
	E[cnt2++] = (Event){-1, cnt1++};
}

int main()
{
	int n;
	ll ans = 0;
	
	scanf("%d", &n);
	rep (i, 0, n)
	{
		ll x, y, r;
		scanf("%lld%lld%lld", &x, &y, &r);
		add(x, y, r, 1);
		add(x, y, r, -1);
	}
	sort(E, E+cnt2);
	rep (i, 0, cnt2)
	{
		Event& e = E[i];
		Arc& a = A[e.k];
		
		if (e.t == -1)
		{
			x0 = a.x - a.r;
			S.insert(e.k);
			if (a.t == 1) continue;
			set<int, Cmp>::iterator it = S.find(e.k);
			if (it == S.begin())
				d[e.k/2] = 1;
			else
				--it, d[e.k/2] = d[*it/2] ^ (A[*it].t == -1);
			ans += (d[e.k/2] ? 1 : -1) * a.r * a.r;
		}
		else
		{
			S.erase(e.k);
		}
	}
	printf("%lld\n", ans);
	return 0;
}