d094. 478 Points in Figures Rectangles ...＠Morris' Blog

2011-09-09 13:14:47| 人氣1,283| 回應0 | 上一篇 | 下一篇

d094. 478 Points in Figures Rectangles ...

推薦 0 收藏 0 轉貼0 訂閱站台

d094. 478 - Points in Figures: Rectangles and Circles, and Triangles
內容：

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

輸入說明：

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

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

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

輸出說明：

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

Point i is contained in figure j

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

Point i is not contained in any figure

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

範例輸入：

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

提示：

Sample Input中圖形及測試點的圖

* 中文翻譯：Lucky 貓

出處：

Uva ACM 478 (管理：MAPLEWING)

作法 :
矩形沒有歪的, 都是正的, 三角形的判定用行列式的正負, 看是否三個都同邊

/**********************************************************************************/
/* Problem: d094 "478 - Points in Figures: Rectangles and Circles, and Triangles" from Uva ACM 478*/
/* Language: C                                                                   */
/* Result: AC(2ms, 268KB) judge by this@ZeroJudge                                */
/* Author: morris1028 at 2011-09-09 12:27:32                                     */
/**********************************************************************************/

#include<stdio.h>
typedef struct {
   char s[2];
   double x1, x2, x3, y1, y2, y3;
   double r;
}D;
D Data[100];
int rectangle(double x, double y, int idx, int in) {
   if(Data[idx].x1 <= x && Data[idx].x2 >= x && Data[idx].y1 >= y && Data[idx].y2 <= y) {
       printf("Point %d is contained in figure %d\n", in, idx+1);
       return 1;
   }
   return 0;
}
double Determinant(double x1, double y1, double x2, double y2, double x3, double y3) {
   return (x1*y2+x2*y3+x3*y1) - (x2*y1+x3*y2+x1*y3);
}
int triangle(double x, double y, int idx, int in) {
   if(Determinant(Data[idx].x1, Data[idx].y1, Data[idx].x2, Data[idx].y2, x, y) *
   Determinant(Data[idx].x1, Data[idx].y1, Data[idx].x2, Data[idx].y2, Data[idx].x3, Data[idx].y3) < 0)
       return 0;
   if(Determinant(Data[idx].x1, Data[idx].y1, Data[idx].x3, Data[idx].y3, x, y) *
   Determinant(Data[idx].x1, Data[idx].y1, Data[idx].x3, Data[idx].y3, Data[idx].x2, Data[idx].y2) < 0)
       return 0;
   if(Determinant(Data[idx].x2, Data[idx].y2, Data[idx].x3, Data[idx].y3, x, y) *
   Determinant(Data[idx].x2, Data[idx].y2, Data[idx].x3, Data[idx].y3, Data[idx].x1, Data[idx].y1) < 0)
       return 0;
   printf("Point %d is contained in figure %d\n", in, idx+1);
   return 1;
}
int circle(double x, double y, int idx, int in) {
   if((Data[idx].x1-x)*(Data[idx].x1-x) + (Data[idx].y1-y)*(Data[idx].y1-y) <= Data[idx].r * Data[idx].r) {
       printf("Point %d is contained in figure %d\n", in, idx+1);
       return 1;
   }
   return 0;
}
void Judge(double x, double y, int n, int test) {
   int i, sum = 0;
   for(i = 0; i < n; i++) {
       switch(Data[i].s[0]) {
           case 'r':sum += rectangle(x, y, i, test);break;
           case 't':sum += triangle(x, y, i, test);break;
           case 'c':sum += circle(x, y, i, test);break;
       }
   }
   if(!sum)
       printf("Point %d is not contained in any figure\n", test);
}
int main() {
   char s[2];
   int in = 0, test = 1;
   double x, y;
   while(scanf("%s", s) == 1 && s[0] != '*') {
       Data[in].s[0] = s[0];
       if(s[0] == 'r')
           scanf("%lf %lf %lf %lf", &Data[in].x1, &Data[in].y1, &Data[in].x2, &Data[in].y2);
       else if(s[0] == 't')
           scanf("%lf %lf %lf %lf %lf %lf", &Data[in].x1, &Data[in].y1, &Data[in].x2, &Data[in].y2, &Data[in].x3, &Data[in].y3);
       else
           scanf("%lf %lf %lf", &Data[in].x1, &Data[in].y1, &Data[in].r);
       in++;
   }
   while(scanf("%lf %lf", &x, &y) == 2, !(x == 9999.9 && y == 9999.9)) {
       Judge(x, y, in, test), test++;
   }
   return 0;
}

我要檢舉

#d094#478#Points in Figures#Rectangles and Circles#and Triangles

台長： Morris

您可能對以下文章有興趣

[UVA] 11284 - Shopping Trip

[UVA][SCC變形] 10510 - Cactus

[UVA][耐心] 10554 - Calories from Fat

[UVA][分析字串] 587 - There's treasure everywhere!

人氣(1,283) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:c103. The Psychic Poker Player
此分類上一篇:d087. 107 - The Cat in the Hat

回應(0)