Difference between revisions of "2015-2016 Petrozavodsk Winter Training Camp, SPb SU + SPb AU Contest"
Jump to navigation
Jump to search
(Created page with "== Problem B == Unsolved. (-2) == Problem C == Unsolved. (-2) == Problem D == Solved by kblack. (+2) == Problem F == Solved by ultmaster. 01:10 (+2) == Problem I == U...") |
|||
| Line 1: | Line 1: | ||
== Problem B == | == 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}$，特别注意与坐标轴平行的线段的计算。 | ||
| + | |||
| + | [[File:20181006_0001.png]] | ||
== Problem C == | == Problem C == | ||
Revision as of 11:40, 6 October 2018
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 (+)