切換
舊版
前往
大廳
主題

ZeroJudge - a871: 11. Museum Area 解題心得

Not In My Back Yard | 2019-08-24 22:03:02 | 巴幣 2 | 人氣 218

題目連結:


題目大意:
給定一正整數 N (3 ≦ N ≦ 10),代表一個凸多邊形的頂點數。接著 N 列輸入,每列給定兩浮點數 x 、 y ,代表其中一個頂點在標準二維座標平面的 x 、 y 座標。

求此多邊形的面積(保證必定小於 2 ^ 31),並四捨五入至小數點後第二位後輸出。



範例輸入:
4
-11 -10
-11 10
11 10
11 -10


範例輸出:
440.00


解題思維:
雖然題目仍然沒有說,但本題的頂點是會依據順序給定的。也就是給定第一個頂點後,接著就是順時針或是逆時針給定其他頂點。

但是如果不是的順序給定的話要怎麼辦呢?當然就是要排序啦。而排序的依據有兩種:
一種是找最凸多邊形最下面的點作為新的座標原點,其他點根據反三角函數各自求出與新頂點的 X 軸之夾角,再根據夾角去排序;
另一種是先將點由 x 座標由小到大排,x 座標一樣的再以 y 座標以小到大排,然後作一次凸包。因為給定的是凸多邊形的頂點,所以凸包的頂點存法等同排序後的原本凸多邊形之頂點。



知道順序後,抓第一個頂點當基準點。然後與每個非相鄰的點連成線,將多邊形分成好幾個三角形,如下圖的例子:
(有一個圈在旁邊的點即為基準點)

接著就是求那些三角形的面積(可用海龍公式、三角函數 + 餘弦定理等等),加總即為凸多邊形的面積之值。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作