bzoj 4561 圆的异或并

Posted on | Views:

扫描线 + $set$ .

  • 把圆看做上下两段半圆弧,因为位置关系只有包含和相离,所以无论 $x$ 取什么值,各个圆弧上下相对顺序是不变的.所以可以将它们全都丢进 $set$ 里面,方便接下来查询.
  • 做一个扫描线,左边插入,右边删除.对于每个圆弧,插入的时候询问它的 $upper_bound$ .
  • 若找到的是上圆弧,说明它就是当前圆外面的第一个圆.
  • 若找到的是下圆弧,说明当前圆外面的第一个圆就是那个下圆弧外面的第一个圆.
  • 可能出现找不到的情况,需要特判.

发现自己好像是第一次写扫描线…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
inline double sq(double x)
{
	return x*x;
}
const int MAXN=2e5+10;
int n;
double x[MAXN],y[MAXN],r[MAXN],pos;
int Sgn[MAXN];
struct LR_Arc
{
	int id,sgn;
	LR_Arc(int id=0,int sgn=0):id(id),sgn(sgn) {}
	bool operator < (const LR_Arc &rhs) const
	{
		return x[id]+sgn*r[id]<x[rhs.id]+rhs.sgn*r[rhs.id];
	}
}q[MAXN<<1];
struct UD_Arc
{
	int id,sgn;//1-up -1-down
	UD_Arc(int id=0,int sgn=0):id(id),sgn(sgn) {}
	bool operator < (const UD_Arc &rhs) const
	{
		int i=id,j=rhs.id;
		double y1=y[i]+sgn*(sqrt(sq(r[i])-sq(x[i]-pos)));
		double y2=y[j]+rhs.sgn*(sqrt(sq(r[j])-sq(x[j]-pos)));
		return y1==y2?sgn<rhs.sgn:y1<y2;
	}
};
set<UD_Arc> S;
set<UD_Arc>::iterator it;
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		x[i]=(double)(read());
		y[i]=(double)(read());
		r[i]=(double)(read());
		q[i*2-1]=LR_Arc(i,-1);
		q[i*2]=LR_Arc(i,1);
	}
	sort(q+1,q+1+2*n);
	for(int i=1;i<=2*n;++i)
	{
		pos=x[q[i].id]+q[i].sgn*r[q[i].id];
		if(q[i].sgn==-1)
		{
			it=S.upper_bound(UD_Arc(q[i].id,1));
			if(it!=S.end())
			{
				UD_Arc tmp=*it;
				if(tmp.sgn==-1)
					Sgn[q[i].id]=Sgn[tmp.id];
				else
					Sgn[q[i].id]=-Sgn[tmp.id];
			}
			else
				Sgn[q[i].id]=1;
			S.insert(UD_Arc(q[i].id,1));
			S.insert(UD_Arc(q[i].id,-1));
		}
		else
		{
			S.erase(UD_Arc(q[i].id,1));
			S.erase(UD_Arc(q[i].id,-1));
		}
	}
	double ans=0;
	for(int i=1;i<=n;++i)
		ans+=sq(r[i])*Sgn[i];
	cout<<(ll)(ans)<<endl;
	return 0;
}