b398.
障礙物轉換
內容
在計算幾何領域中，機器人規劃路線是一個實用的議題， 由於機器人是一個有體積的物體，要避開其他的障礙物，障礙物碰撞計算會變得相當複雜。由於某 M 沒有學好這一部分，知道一種方法可以將地圖轉換，把機器人轉換成一個點，計算得到新的障礙物，如此一來就不用處理障礙物碰撞。
從上圖中，一個箭頭型機器人要從左下角移動到右上角，假設不考慮物體可以旋轉，請問是否能移動過去。若把機器人當作一點看待，則必須將物體邊緣增加，變成中間那張圖 configuration space，只剩下一個點和數個多邊形障礙物。接著可以轉換成 visibility graph，把剩下的白色空間進行梯形剖分或者三角剖分，將區域表示成一個點，相鄰區域拉一條邊，就成 dual graph，就能套用一般的最短路徑算法，來協助機器人行走。
處理這問題對於某 M 過於困難，於是將問題更簡化些，只需要把中間那一張圖其中一個障礙物變化求出即可。
現在給定一個凸多邊形障礙物以及移動凸多邊形，假設定位點在深黑色點方形部分，藉由貼著障礙物可以構出新的障礙物，請問新的障礙物為何？
輸入說明
第一行會有一個整數 T，表示有多少組測資。
每一組測資會包含兩個凸多邊形。第一行有一個整數 N 表示移動凸多邊形的頂點數量，接下來會有 N 行，每一行會有兩個整數 x, y 表示頂點座標。在 N+1 行之後，會有一個整數 M 表示障礙物凸多邊形的頂點數量，接下來會有 M 行，每一行會有兩個整數 x, y 表示頂點座標。
- 2 < N, M < 512
- -32767 < x, y < 32767
- 假設定位點 (深黑色點方形部分) 都設在原點 (0, 0)。
- 輸入順序會按照順時針或逆時針給定。
輸出說明
對於每一組測資，輸出一行轉換過後的凸多邊形面積 (本來可以求出頂點座標，為簡化輸出而設計)。
範例輸入
#1
2 5 -1 -1 -1 1 0 3 1 1 1 -1 4 1 1 8 2 12 -1 6 -4 3 -1 -4 -1 1 1 1 5 1 0 6 5 10 5 10 -3 1 -3
範例輸出
#1
Case #1: 89.0 Case #2: 115.5
測資資訊：
記憶體限制：
128
MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 3.0s , <1M
公開 測資點#2 (20%): 3.0s , <1M
公開 測資點#3 (20%): 3.0s , <1M
公開 測資點#4 (20%): 3.0s , <1M
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 3.0s , <1M
公開 測資點#2 (20%): 3.0s , <1M
公開 測資點#3 (20%): 3.0s , <1M
公開 測資點#4 (20%): 3.0s , <1M
提示 ：
所求面積為橘色部分為 89。
關鍵字搜索： Minkowski Sum
出處:
妮可
[管理者：
morris1028
(碼畜)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||