d094. 00478 - Points in Figures: Rectangles and Circles, and Triangles

Content

在x-y平面上，給你一些圖形（矩形、圓形、三角形）和一些點，請你回答這些點落在哪些圖形內（如果有的話）。另外，在這個問題中，剛好落在邊上的點不視為落在該圖形內。

Input

首先是圖形的資料，每個圖形一列，第1個字元代表圖形的類別（r 代表矩形，c 代表圓形，t 代表三角形），如果該圖是矩形，接下來會有4個數值分別代表該矩形左上角及右下角的座標。如果該圖是圓形，接下來會有3個數值分別代表該圓的圓心座標及半徑。如果該圖是三角形，接下來會有6個數值分別代表該三角形的三頂點座標。圖形的個數不會超過10個。

以一列僅含有一個*代表圖形資料結束。

接下來的每列為一個點的座標，也就是要測試的點。若點座標為9999.9 9999.9代表輸入結束（此點不需輸出）。請參考Sample Input。

Output

對每一個測試的點，若其落在某圖形內，則輸出下列格式的訊息：

Point i is contained in figure j

如果某個點沒有落在任何圖形內，則輸出：

Point i is not contained in any figure

請注意：點和矩形的編號是按照他們出現在input的順序。請參考Sample Output

Sample Input #1

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

Sample Output #1

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

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (50%): 1.0s , <1M
公開測資點#1 (50%): 1.0s , <1M

Hint ：

Sample Input中圖形及測試點的圖

* 中文翻譯：Lucky 貓

Tags:

出處:

UVa 478 [管理者： MAPLEWING (灆洢騎士) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」