2011-09-09 13:14:47Morris
d094. 478 Points in Figures Rectangles ...
d094. 478 - Points in Figures: Rectangles and Circles, and Triangles
內容 ：
/**********************************************************************************/
/* 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;
}
內容 ：
在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 貓
出處
：
/**********************************************************************************/
/* 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;
}