b398. 障礙物轉換
標籤 : 凸包 單調 計算幾何
通過比率 : 10人/11人 ( 91% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-06-15 06:24

內容

在計算幾何領域中,機器人規劃路線是一個實用的議題, 由於機器人是一個有體積的物體,要避開其他的障礙物,障礙物碰撞計算會變得相當複雜。由於某 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
提示 :

所求面積為橘色部分為 89。

關鍵字搜索: Minkowski Sum

標籤:
凸包 單調 計算幾何
出處:
妮可 [管理者: morris1028 (碼畜) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」