2015-2016 Petrozavodsk Winter Training Camp, SPb SU + SPb AU Contest

Problem B

Upsolved by kblack. (-2)

题意：给出平面上 $N$ 个点，他们相互连接的 $\binom{N}{2}$ 条线段与 $x$ 轴夹角的中位数。

题解：我们需要知道中位的一个或两个线段的夹角，考虑二分答案，问题转化为求夹角小于 $\theta$ 的线段的数量。如图，我们从右往左枚举点，并计算处于某个点 $A$ 区域的点数，计算方式是用 $l_1$ 右侧（枚举顺序）和 $l_2$ 下侧（排序）夹出 $B+C$，同理用 $l_1$ 右侧和 $l_3$ （顺时针旋转 $\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 (+)