赤橙黄绿
青与兰
考虑画一个十字形,把第 $1,3$ 象限和第 $2,4$ 象限分别匹配,红点是 $(0,0)$,如果蓝点和黄点的数量匹配就匹配成功。
如果确定了十字形的角度,那么两条分割线的位置是确定的(必须把点分成两半),因此可以 check 一个角度是不是可行的。
这样分点之后,第一象限点数 = 第三象限点数,第二象限点数 = 第四象限点数。
设差值 $c$ 为 第一象限蓝点数 - 第三象限黄点数。则 $-c$ 为 第二象限蓝点数 - 第四象限黄点数。
若 $c=0$ 则找到了能匹配成功的角度。
考虑角度从 $\alpha = 0$ 转到 $\alpha = \frac{\pi}{2}$,那差值会从 $c$ 变到 $-c$,并且在转动过程中每次只会 $\pm 1$,一定有一个角度差值为 $0$。
二分求这个角度即可。具体的,假设 $c_l > 0, c_r < 0$,我们求出 $c_{mid}$,不断取 $c_l \times c_r < 0$ 的区间。
算 $c_{\alpha}$ 需要排序,时间复杂度 $O(n\log n\log V)$。(也可以 nth_element,$O(n\log V)$)