IOI 2005 Garden

對於任何長方形的放法, 總有方法用一條橫/直線把它們分開
做法就是窮舉那條分界線

先假設是打橫切
問題就變為在 row[x..y] 中要包住 k 支roses 的長方形的最小邊長

先 pre compute 長方形的邊 exactly 由 row x 到 row y 的情況
然後用兩條掃描線就可以了

總時間O(N³)