Qglin_ 的網誌

網誌

普及组入门赛 T4 题解

2019-11-02 22:25:01 By Qglin_

先推出结论:如果一个圆在偶数个圆内,则把它的面积加入答案;在奇数个圆内则从答案中减去它的面积。

测例1~3:花 $O(N^2)$ 求出圆的两两包含关系。

测例4~6:采取一些处理可以减少判断包含关系的次数。例如外接正方形相离则必然相离;若 $A$ 包含 $B$,$B$ 包含 $C$,则能得出 $A$ 包含 $C$,进一步还可以知道包含关系其实构成了一棵树,利用传递性能减少部分工作量。

测例7~10:

一个圆被另一个圆包含当且仅当圆心被包含。

一个点被x个圆包含当且仅当该点作出任意一条射线和 $x$ 个圆相交。

每个圆心作同方向的射线(如都向 $x$ 轴正方向),用这些射线所在的直线做扫描线。

每条扫描线上,与每个圆的交点构成括号序列,按 $y$ 从小到大枚举这些扫描线。

随着扫描的进行,有些圆表示的括号会插入进序列,有些会从序列中删除。由于圆之间没有交点,不同圆之间的括号顺序不会交换;而且插入和删除时也一定成对出现。

用平衡树维护括号序列,插入括号对、删除括号对、查询某个射线的时候在平衡树上寻找其位置。

Qglin_ Avatar