Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

　　李先生擁有一棟別墅，由於浴室的地板磁磚已經老舊，因此他想要自己動手重新貼上漂亮的磁磚。他開著車子去買正方形磁磚，當他挑選好想要的磁磚後卻不知道如何擺置才好看，於是老闆就配色上的美觀給了他一些建議，他回到家後，就老闆的建議開始對磁磚擺置做規劃。
　　假設李先生挑選了 n 個長、寬皆為 w 的正方形磁磚，每個磁磚顏色都不同，並將磁磚編號為 1, 2, …, n。老闆的建議是每個磁磚必須沿著水平線與垂直線擺放 (即不能旋轉)，同時任二個磁磚的位置必存在一種相對關係 (即上下或左右關係)。假設 i(1 ≤ i ≤ n)、j(1 ≤ j ≤ n , i ≠ j) 為任兩片磁磚的編號，(x_i, y_i)、(x_j, y_j) 分別表示 i、j 這兩片磁磚擺放後的左下角座標，(x_i+w, y_i+w)、(x_j+w, y_j+w) 分別表示它們擺放後的右上角座標。當老闆建議將 i 放在 j 的右邊時，則於完成磁磚擺放後，必須滿足 x_j+w ≤ x_i；當老闆建議將 i 放在 j 的上面時，則於完成磁磚擺放後，必須滿足 y_j+w ≤ y_i。此外，相對位置的關係具有可傳遞性，例如：磁磚 i 被建議放在磁磚 j 的上面，磁磚 j 被建議放在磁磚 k 的上面，則磁磚 i 一定被建議放在磁磚 k 的上面；但是不會出現矛盾情形，例如：磁磚 i 被建議放在磁磚 j 的上面，且磁磚 j 被建議放在磁磚 k 的上面，則不會出現將磁磚 k 放在磁磚 i 上面的建議。此外，為了節省浴室空間，李先生希望能將這些磁磚擺置於一個矩形 (含正方形) 區域內，而且該區域的面積要越小越好。
　　為了節省時間，李先生希望你能幫忙寫一個程式，規劃出一個符合老闆建議 (即每個磁磚必須沿著水平線與垂直線擺放，並滿足 n(n-1)/2 種磁磚相對位置關係) 的磁磚擺置方式，而且包圍這個磁磚擺置方式的矩形面積必須是所有滿足老闆建議的擺置方式中的最小值。你的程式必須算出該最小面積，回報給李先生。
　　以下為一範例：假設李先生購買了 4 個長、寬皆為 1 的正方形磁磚，並將磁磚編號為 1~4，按照老闆的建議，這些磁磚的相對位置關係如下：2 要擺在 4 的右邊、1 要擺在 4 的上面、1 要擺在 2 的上面、3 要擺在 1 的上面、3 要擺在 4 的上面、和 3 要擺在 2 的上面。下圖列出四種滿足老闆建議的擺置方式，其中後二種方式 ((c) 與 (d)) 可分別用面積為 9 的矩形區域將其圍住，而前二種方式 ((a) 與 (b)) 則分別只需用面積為 6 的矩形區域將其圍住。就本範例而言，所有滿足老闆建議的擺置方式中最小的矩形面積為 6 ，所以你的程式必須回報 6 給李先生。

輸入範例 1:
4
1
2 4 0
1 4 1
1 2 1
3 1 1
3 4 1
3 2 1

輸入範例 2:
6 
3 
2 1 0
3 2 0
3 1 0
6 4 0
4 1 1
5 1 1
4 2 1
5 2 1
4 3 1
5 3 1
5 4 1
6 1 1
6 2 1
6 3 1
5 6 1

輸出範例 1:
6

輸出範例 2:
81