2015-2016 Petrozavodsk Winter Training Camp, SPb SU + SPb AU Contest
Problem B
Upsolved by kblack. (-2)
题意:给出平面上 $N$ 个点,他们相互连接的 $\binom{N}{2}$ 条线段与 $x$ 轴夹角的中位数。
题解:我们需要知道中位的一个或两个线段的夹角,考虑二分答案,问题转化为求夹角小于 $\theta$ 的线段的数量。如图,我们从右往左枚举点,并计算处于某个点 $A$ 区域的点数,计算方式是用 $l1$ 右侧(枚举顺序)和 $l2$ 下侧(排序)夹出 $B+C$,同理用 $l1$ 右侧和 $l3$ (顺时针旋转 $\theta$ 后排序)下侧夹出 $A+B+C$,树状数组维护一下,减一下就得到了 $A$ 区域的点数。这个方法只作用 $0 \leq \theta \leq \frac{\pi}{2}$,如果线段数不够,我们可以直接将整个平面顺时针旋转 $\frac{\pi}{2}$,特别注意与坐标轴平行的线段的计算。
Problem C
Unsolved. (-2)
Problem D
Solved by kblack. (+2)
Problem F
Solved by ultmaster. 01:10 (+2)
Problem I
Unsolved. (-3)
Problem J
Solved by ultmaster. 03:13 (+)
Problem K
Solved by zerol. 01:39 (+)