數學/演算法：正方形內有5個點，為什麼最近點對的距離小於邊長？

01-14

一個點位於左邊的三角形中，另一個點位於右邊的三角形中，距離為兩點之間的連線（例如pq）
而在左右兩個d*d正方形區域內，最多都只能含有4個點。如果超過4個點，則這個正方形區域內至少存在一個點對的距離小於d。

以上的結論需要如何證明呢？
------------------------------------------------------
以上的問題是我從《編程之美》的求兩點之間最短距離抽出的一個知識點，如果看過這本書的朋友有沒有遇到以上問題呢=。=書上直接就給出結論了，怎麼想都不明白

樓上的證明看起來比較繁瑣，我來個簡單的。

把正方形4等分成4個小正方形，邊長d/2。由抽屜原理，5個點中，至少有兩個點在同一個小正方形里，這兩個點距離最大不超過 $frac{sqrt{2}}{2}d<d$ ,證完。

可以用反證法，假設正方形 $ABCD$ 內含有4個以上的點，這些點兩兩之間的距離大於或等於 $d$

考慮這些點中的4個點 $EFGH$ ，四個點兩兩之間的連線線段有6條，這6條線段兩兩相交於這4個點有12個夾角，我們能證明這12個夾角必有一個角大於或等於90度。於是由余弦定理得到有兩點間的距離大於或等於 $sqrt{2} d$ ，從而證明了這個四個點只能分布在正方形的四個頂點上，又第5個點也在正方形的內部，它到這4個點的距離不可能都大於或等於 $d$ ，因此假設不成立，命題得證。