一道趣題：如何通過調整角度使探照燈照亮整個平面？

12-10

在平面上任意的n個定點上，放置了n個點光源,每個光源可以照亮圓心角為2*π/n的一個扇形區域。

證明通過調整點光源的照射角度，一定可以使這n個點光源照亮整個平面。

經三鮮同學提醒，大於pi的情況疏忽了。重新寫一個更詳細的算了。
——————————————
如果n=1或n=2，成立顯然，以下考慮n&>=3的情況。
定義

楔形wedge：從一點出發的兩條射線圍成的類似扇形的區域（但是無限延伸），稱兩條射線的夾角為楔形的張角，這個點為楔形的頂點。
楔形的補complementary wedge：把這兩條射線反向，圍成的楔形（類似對頂角）。注意補的張角和原張角是相等的，和普通的補不一樣，相當於旋轉180度。

一個光源可照亮的範圍，就是張角為 $2pi/n$ 的一個楔形。
題目要求照亮整個平面，下面證明的思路是：

先考慮特殊情況：對於張角 $leqpi$ 的楔形區域，假如光源在其補中，可以完全覆蓋這個楔形。
但是我們需要照亮整個平面，平面可看做張角為 $2pi$ 的楔形，很遺憾不能直接用引理1。我們希望對於任意放置的光源，能夠將平面分割為若干特別的張角 $leqpi$ 的楔形，這樣：
用1中的結論，每個楔形里的光源都可照亮其補。於是整個平面被完全覆蓋。

——————————開始——————————
引理1

給出一楔形 $W$ ，設其張角為 $heta$ ，在其補 $W$ 中有 $k$ 個光源（各自位置任意給定），每個點可照亮張角為 $heta/k$ 的楔形。則可以調整它們照射的角度，使其覆蓋 $W$ 。

可用歸納法證明,畫出k=1的情況防止誤解。

引理2

令 $p=lfloor n/3 floor, q=n-2p, heta=2ppi/n,phi=2qpi/n.$ 對於任意放置的光源，都可將找到一個點，以其為頂點可做出張角分別為 $heta, heta,phi$ 的三個楔形 $W_1,W_2,W_3$ ，各包含 $p,p,q$ 個光源。通俗地說，就是把平面近似平均切成了三塊，每塊近似包含了三分之一的光源，並且每塊包含的光源能照亮的角度之和與楔形張角相等。「近似」是由於需要取整。

證明：
隨意安排這三個楔形的順序和邊界的方向。假設像這個樣子：

下面，邊界的方向固定，尋找這個合適的頂點。
把直線 $l_1$ 從最下方慢慢向上移動。由於 $W_1$ 要有 $p$ 個光源，所以 $l_1$ 右下的光源數要大於等於 $p$ ，類似，左上的光源數大於等於 $q$ ，這樣限制了 $l_1$ 的範圍。做出 $W_1,W_3$ 使其恰好包含 $p,q$ 個光源，設交點分別為 $x_1,x_2$ 。如果 $x_1,x_2$ 重合，則得解。如果不重合：
$x_1,x_2$ 看做數軸的點。 $l_1$ 處於最下方時，右下恰有 $p$ 個光源， $x_1$ 可以取得任意小，直到小於 $x_2$ ：

$l_1$ 處於最上方時，左上恰有 $q$ 個光源， $x_2$ 可以取得任意小，直到小於 $x_1$ ：

當 $l_1$ 向上移動時，由連續性，必有 $x_1,x_2$ 可行域重合時。相交時即找到目標頂點，由此可將平面三分。定理（目標）：
由引理2，我們可將平面三分，三分是保證每個楔形的張角都不大於 $pi$ ，以利用引理1；由引理1，每個楔形的光源可完全覆蓋這個楔形的補，這些補合起來就是完整平面，這樣就得到了照亮完整平面的方法。證完。
程序實現，引理2中三分平面用時 $O(nlog n)$ , 引理1用時 $O(n)$ ，總體 $O(nlog n)$ 。

floodlight problem

如果不是我看錯題目的話，難道不是把所有光源放在一起平均向外射？
=====================
如果光源的位置是固定的，那還是平均向外射，這個時候就看成光源從【某個點】向後退。既然都集中在一個點平均向外射可以覆蓋整個平面，每個光源向後退覆蓋的範圍會更大而且嚴格覆蓋原先的範圍，所以肯定是可以100%覆蓋的。