題目連結:
輸入有兩部分,第一與第二部分以一個「*」作分隔。
第一部分有若干列,每列開頭給定一個字元。字元只會是「r」、「c」、「t」,分別代表這列給定的圖形是矩形、圓形或是三角形。(三種圖形的總個數不會超過 10 個)
如果字元是「r」,則接著會給定四個浮點數,代表此矩形的左上角以及右下角的 x 、 y 座標;如果字元是「c」,則接著會給定三個浮點數,代表此圓形的圓心 x 、 y 座標以及半徑;
如果字元是「t」,則接著會給定六個浮點數,代表此三角形三點的 x 、 y 座標。
而第二部分也有若干列,每列給定兩浮點數(如果兩浮點數之值皆為 9999.9 ,則代表輸入結束),代表一個點的 x 、 y 座標。判斷此點是否有在任何給定的圖形內(剛好在圖形上,不算作在「內部」)。
如果有在圖形裡,每一個圖形皆請輸出「Point i is contained in figure j」,其中 i 代表這個點是第二部分給定的第幾個點、 j 代表的是該圖形是第一部分給定的第幾個;如果沒有在任何圖形裡,請輸出「Point i is not contained in any figure」。
r 8.5 17.0 25.5 -8.5
c 20.2 7.3 5.8
t -1.0 -1.0 10.1 2.2 .4 1.4
r 0.0 10.3 5.5 0.0
c -5.0 -5.0 3.7
t 20.3 9.8 10.0 -3.2 17.5 -7.7
r 2.5 12.5 12.5 2.5
c 5.0 15.0 7.2
t -10.0 -10.0 10.0 25.0 30.0 -10.0
*
2.0 2.0
4.7 5.3
6.9 11.2
20.0 20.0
17.6 3.2
-5.2 -7.8
9999.9 9999.9
Point 1 is contained in figure 4
Point 1 is contained in figure 9
Point 2 is contained in figure 4
Point 2 is contained in figure 7
Point 2 is contained in figure 9
Point 3 is contained in figure 7
Point 3 is contained in figure 8
Point 3 is contained in figure 9
Point 4 is not contained in any figure
Point 5 is contained in figure 1
Point 5 is contained in figure 2
Point 5 is contained in figure 6
Point 5 is contained in figure 9
Point 6 is contained in figure 5
Point 6 is contained in figure 9
這題需要一些幾何學以及一些浮點數的知識。首先,判斷一個點在圓內和矩形內應該都不難,一個是判斷點與圓心的距離是否小於半徑;一個是點是否在矩形左上頂點的右下方且在右下頂點的左上方。
比較難判斷的是三角形,但是也沒有多複雜——如果在三角形內部,則此點會將此三角形分成三個小的三角形;如果在三角形上,則會分成 < 3 個三角形;如果在外部,則無法將該三角形作分割。
因此就是判斷此點與三角形任意挑兩點與其作出三角形(3 挑 2 ,所以總共生成 3 個三角形),這些三角形的面積和是否原本的三角形。如果面積和 =本來三角形的面積且這些三角形沒有一個是面積為 0 的,則此點在三角形內部;反之,則不是。
而三角形面積算法可以使用海龍公式或是行列式值去算。
但是因為上述所有值(包含座標值)皆是浮點數,所以容易產生浮點數誤差。尤其,題目要求在圖形「上」的點不算作在內部。
因此我們可以定義一個誤差值 E 並假設我們要判斷 a 是否等於 b ,則如果 a + E ≧ b 且 a - E ≦ b ,我們就算作 a = b ;反之,a ≠ b 。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。