從一題幾何題的啟發

這次（2023）幫 PCCA Camp 出題的過程中，發現這題有延伸的定理和題目。我也覺得這幾題都滿酷的，順便紀錄一下

Disclaimer: 底下有 PCCA Winter Camp 2023 題目的暴雷，想 vir 的請先右轉謝謝（之後應該會把題目放在 Gym 上）

這是 PCCA Winter Camp 2023 pL，我幫忙出的題目：

給你平面上不重複的 $n$ 個點，任三點不共線。請你找到兩條線，使得分成的 $4$ 個區域各有 $n/4$ 個點。

注意到上面任三點不共線的條件很重要，不然是有可能無解的。考慮 $8$ 點共線的情況，這樣子解就一定不存在。

這題有很多解法，其中我的解法最關鍵的地方用到這個性質：考慮兩條垂直的線，兩條線兩邊都各有 $\frac{n}{2}$ 個點。則一定存在一個角度，使得旋轉這個角度並且保持兩邊各有 $\frac{n}{2}$ 個點以後會是解。（證明的部份先扣著，下面會提到主要證明的類似想法）不過後來 toxicpie 給了一個解法差不多的 general 版本，這次就打算介紹這個版本。也感謝 toxicpie 的介紹 ><。

題目介紹

給你平面上不重複的 $n$ 個紅點和 $m$ 個藍點，任三點不共線。請你找到一條線使得紅藍兩點集都被平分。

這裡假設 $n$ 和 $m$ 都是偶數。$n$ 和 $m$ 是奇數或有多點共線的情況也有相對應的定義，在下面的維基百科中有提到。容易看得出來上面那個問題是這個問題的 special case。

在數學中這題的連續版本更為出名：$n$ 個 $n$ 維物體，一定存在一個 $n-1$ 維的超平面能夠把他們評分。這個定理有一個形象化的名字叫 Ham sandwich theorem（想像有一個火腿三明治有兩片麵包和一片火腿，那一定有一刀能夠把這三個物體同時切成兩半）。不過這次沒打算介紹這個定理的證明就是了，數學太爛看不懂 QQ。

證明

這裡只提供一個很不嚴謹的證明想法。對於每個角度 $\theta$（$0 \leq \theta \leq \pi$），我們用一條角度是 $\theta$ 的線把紅色點集切開。令 $f(\theta)$ 是這條線其中一邊有多少個藍色點。注意到線的選擇其實不只一種，這裡假設線會貼住中間兩個的前一個。

則可以注意到一件事：$f(0) + f(\pi) = m$，也就是 $\frac{m}{2}$ 會剛好介在 $f(0)$ 和 $f(\pi)$ 之間。而又可以發現 $f$ 是連續變化的，每次都只會 $+1$ 或 $-1$，則說明了一定存在一個 $x$ 使得 $f(x) = \frac{m}{2}$。

當然以上說明有一些漏洞要補，比方說為什麼 $f$ 是連續變化的，就 Left to reader as an exercise（X），或者是下面有一些我進一步的想法。

證明想法的其他應用

可以觀察到上面主要的想法其實就是 intermediate value theorem 的離散版。我覺得這個想法很酷，想法簡單卻可以解決很多看似很難的問題。例如這題分點問題也是這個想法的應用。甚至也可以用在一些其他場合例如這題 Codeforces Div.2 F。

演算法

從演算法角度來看，我們能夠找到另一種解釋。在固定 $\theta$ 的時候，我們可以對所有 $n+m$ 個點排序，用固定斜率下，線「掃過去」碰到點的順序來決定。則可以發現 $\theta=0$ 的時候和 $\theta = \pi$ 的時候點的序列會剛好是反過來的。注意到平分紅色或藍色點集的線的範圍是這個序列的一個區間（也就是兩個顏色各自中間兩個點之間的那個範圍），當從 $\theta = 0$ 到 $\theta = \pi$ 時兩者的順序會調換。而也可以注意到角度變化時每次也就是相鄰兩個點交換順序，因此總有一個時候兩個區間會有重疊，那重疊部份就是答案。

到這裡我們就可以幾乎提出一個演算法了：我們可以把所有點對之間的斜率排序，同時維護兩個區間在整個序列出現的位置。在一邊交換相鄰順序的同時維護兩個區間，兩個區間重疊時就停下來輸出答案。總時間複雜度 $\mathcal{O}(n^2 \log n)$。

Wiki 說這題可以做到 $\mathcal{O}(n \log n)$，不過我也不知道怎麼做就是了。

至於實作的話等之後補 PCCA pL 再說吧。

結論

總之我覺得這是一個很有趣的問題，也沒想到全點對斜率除了找最小三角形面積之類的題目以外還有這種應用 OwO