主題

ZeroJudge - f425: 高雄市109年資訊競賽國中組第三題 解題心得

Not In My Back Yard | 2020-11-22 00:00:02

題目連結:


題目大意:
輸入有三列,每列給定兩整數 x 、 y (|x| 、 |y| ≦ 100),這三列代表著一個三角形的三頂點之座標值(保證是合法的三角形,即三點不共線、不為同一點)。

請輸出該三角形的面積兩倍之值。



範例輸入:
範例輸入一:
2 1
8 2
12 9

範例輸入二:
6 4
-5 -6
8 6

範例輸入三:
0 0
0 1
1 0


範例輸出:
範例輸出一:
38

範例輸出二:
2

範例輸出三:
1


解題思維:
這題也是一題數學題(而且是幾何相關)。

雖然海龍公式(Heron's Formula)可以算出三角形的面積,但可能會因為浮點數誤差而錯誤。因此,我們需要以下公式
a × b × sin(C) ÷ 2
其中 a 、 b 為三角形兩邊, C 為 a 、 b 兩邊夾出的角。因為我們要輸出的是面積的兩倍,所以尾端的「÷ 2」可以省略。

乍看之下,還是會有浮點數誤差。但是因為叉積(Cross Product,也稱作外積)的性質——向量 a (這邊不再是如上面的邊,而是向量)與向量 b 之叉積「值之大小」恰好為 |a| × |b| × sin(C)。

我們假設給定的輸入座標分別為 x1 、 y1 、 x2 、 y2 、 x3 、 y3 且定義 X1 = x2 - x1 、 Y1 = y2 - y1 、 X2 = x3 - x1 、 Y2 = y3 - y1,而向量 a 定為 (X1, Y1, 0) 、 向量 b 定為 (X2, Y2, 0),則 a 與 b 之叉積為
(0, 0, X1 × Y2 - X2 × Y1)
注意叉積這個操作完後得到的還是一向量,因此我們需要取其大小,而前兩個座標值皆為 0 所以可以直接看第三個座標值。將該座標值取絕對值即是所求。

不過,本題原本是出給國中生,所以其實用海龍公式就好了。



題外話:
三維空間與外積確定是高中的課程,但是原來海龍公式是國中的範圍啊?我記得我是高中才知道海龍公式的QQ




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
51 巴幣: 0
屠屠
結果我還是用了海龍公式 不過我將公式做了整理得到這個公式https://truth.bahamut.com.tw/s01/202012/b64b424de0f9e1fa796d6366b38ce403.PNG也就是說計算距離時得到距離的平方不用開根號 套用這個公式後就不會有不精準問題
2020-12-07 23:42:42
屠屠
更正圖片https://truth.bahamut.com.tw/s01/202012/eadb5afd0708dcc6a1b18c018082dd35.PNG
2020-12-07 23:52:41

相關創作

更多創作