Problem
在計算幾何領域中，機器人規劃路線是一個實用的議題， 由於機器人是一個有體積的物體，要避開其他的障礙物，障礙物碰撞計算會變得相當複雜。由於某 M 沒有學好這一部分，知道一種方法可以將地圖轉換，把機器人轉換成一個點，計算得到新的障礙物，如此一來就不用處理障礙物碰撞。
從上圖中，一個箭頭型機器人要從左下角移動到右上角，假設不考慮物體可以旋轉，請問是否能移動過去。若把機器人當作一點看待，則必須將物體邊緣增加，變成中間那張圖 configuration space，只剩下一個點和數個多邊形障礙物。接著可以轉換成 visibility graph，把剩下的白色空間進行梯形剖分或者三角剖分，將區域表示成一個點，相鄰區域拉一條邊，就成 dual graph，就能套用一般的最短路徑算法，來協助機器人行走。
處理這問題對於某 M 過於困難，於是將問題更簡化些，只需要把中間那一張圖其中一個障礙物變化求出即可。
現在給定一個凸多邊形障礙物以及移動凸多邊形，假設定位點在深黑色點方形部分，藉由貼著障礙物可以構出新的障礙物，請問新的障礙物為何？
Input
第一行會有一個整數 $T$，表示有多少組測資。
每一組測資會包含兩個凸多邊形。第一行有一個整數 $N$ 表示移動凸多邊形的頂點數量，接下來會有 $N$ 行，每一行會有兩個整數 $x, y$ 表示頂點座標。在 $N+1$ 行之後，會有一個整數 $M$ 表示障礙物凸多邊形的頂點數量，接下來會有 $M$ 行，每一行會有兩個整數 $x, y$ 表示頂點座標。
- $2 < N, M < 512$
- $-32767 < x, y < 32767$
- 假設定位點 (深黑色點方形部分) 都設在原點 (0, 0)。
- 輸入順序會按照順時針或逆時針給定。
Sample Input
|
|
Sample Output
|
|
Hint
Solution
可以用 $O(nm \log nm)$ 來完成此題，方法很簡單，先將機器人的圖形按照原點旋轉 180 度，接著將障礙物每一個頂點座標加上機器人的座標，總共會得到 $nm$ 的頂點，套用凸包算法求一次即可。
這一題應用 Minkowski Sum 來完成，對於兩個凸多邊形的 Minkowski Sum，可以在 $O(n+m)$ 時間內完成，將兩個凸包採用逆時針儲存，挑選最左，等價時抓下方 y 座標的點，可以知道新凸包的頂點一定是由兩個凸包的頂點$A_i, B_j$ 疊加而成，一開始抓到的左下方頂點疊加可以得到第一個頂點，接著要按照凸包順序求出，則比較$(A_i, A_{i+1})$ 和$(B_j, B_{j+1})$ 哪一個偏的角度小，就挑選哪一個往前推動 i = i+1 或者是 j = j+1。最後就能在 $O(n+m)$ 時間內完成。
假設不是凸多邊形，兩個簡單多邊形最慘會到 $O(n^2 m^2)$。
|