主題
題目連結：
題目大意：
輸入有兩部分，第一與第二部分以一個「*」作分隔。
第一部分有若干列，每列開頭給定一個字元。字元只會是「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 。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
