Largest Empty Rectangle

Largest Empty Rectangle

問題:一張紙上有許多點,請在紙上畫出不包含任何點的矩形,且面積最大者。

這裡僅簡單講一下,等我心血來潮的時候,再來將文章寫的詳細點。

方法是:將紙張上面的每一個點,都嘗試當做矩形的左邊界。固定左邊界之後,依序掃描在其右的點,並一一當做矩形的右邊界;固定左右邊界後,便可找出一個最大的長方形。最後再次照上面的流程,左右整個顛倒再跑一次,即可找出Largest Empty Rectangle。

還要另外處理一下特別的情況──長方形的左右邊界恰好是紙的左右邊界。在紙張的四個角落都先補上點,就會比較好處理。

時間複雜度是O(N^2),N為黑點的數目。【待補程式碼】

UVa 10043