【bzoj1043】下落的圆盘
题意
有n个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红色线条的总长度即为所求.
\(1\leq n\leq 1000\)
分析
自己在做这一道题的时候有种想法：
由于我们的精度有一定的限制。
所以我们把这幅连续的图离散成一个个微小的点。
然后不断染色。
然而由于图太大了，无法存下。
这种Trick就不成立喽。
换一种想法。
我们考虑枚举每一个圆，求它在最后剩下的弧的总长度，然后所有相加即可。
最后剩下的，就是在后面的圆作用下，仍然留下来的，设由\(\alpha\)度留下来，那么贡献为\(\alpha r\)。
根据容斥原理，我们只需要求出在后面的圆作用下，被覆盖的度数\(\beta\)，然后贡献为\((2\pi-\beta)r\)。
以我们当前枚举的圆的圆心为源点，建立平面直角坐标系。
那么我们考虑之后每一个圆对其的影响，设当前圆为\(a\)，之后圆为\(b\)。
情况1：当前圆被完全覆盖，若出现，那么这个圆就废掉了，直接退出；
情况2：当前圆把之后圆完全覆盖，那么之后的圆就不会对当前的圆产生影响；
情况3：当前圆与之后圆不相交，那么也不会产生影响；
情况4：当前圆与之后圆相交。我们要求出：交点，交点与\(x\)轴的夹角。至于怎么求，真的只能自己YY了，连接点\(a\)与点\(b\)，把弧分割成线段ab与\(x\)轴的夹角和一个知道三边边长的三角形的夹角，第二部分用余弦定理解决，没有图很难说清。一段弧被表示成了一段区间，然后排一次序，扫一遍就好了。
代码
待完善。
小结
（1）浮点误差
涉及到浮点误差的几何问题或代数问题，通常可以把平面或者空间进行离散，离散成微小的点，进行大概率正确性的转化。