投資錢景>買台積電就對了5檔高息股比定存強10倍法人:14檔今年本業虧定了老伯送飲料 遭學生糾察...
2012-07-06 08:50:04 人氣(166) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA] 478 - Points in Figures: Rectangles ...

0
收藏
0
推薦


 Points in Figures: Rectangles, Circles, and Triangles 

Given a list of figures (rectangles, circles, and triangles) and a list of points in the x-y plane, determine for each point which figures (if any) contain the point.

Input

There will be n(Ÿ 10) figures descriptions, one per line. The first character will designate the type of figure (``r'', ``c'', ``t'' for rectangle, circle, or triangle, respectively). This character will be followed by values which describe that figure.

  • For a rectangle, there will be four real values designating the x-y coordinates of the upper left and lower right corners.
  • For a circle, there will be three real values, designating the x-y coordinates of the center and the radius.
  • For a triangle, there will be six real values designating the x-y coordinates of the vertices.
The end of the list will be signalled by a line containing an asterisk in column one.

The remaining lines will contain the x-y coordinates, one per line, of the points to be tested. The end of this list will be indicated by a point with coordinates 9999.9 9999.9; these values should not be included in the output.

Points coinciding with a figure border are not considered inside.

Output

For each point to be tested, write a message of the form:

Point i is contained in figure j
for each figure that contains that point. If the point is not contained in any figure, write a message of the form:
Point i is not contained in any figure
Points and figures should be numbered in the order in which they appear in the input.

Sample Input

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

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

Diagrama of sample input figures and data points




#include <stdio.h>
#define eps 0
typedef struct {
    double x, y;
} Point;
typedef struct {
    Point a, b, c;
    double r;
    int sh;
} Shape;
Shape D[1000];
double cross(Point &o, Point &a, Point &b) {
    return (a.x - o.x)*(b.y - o.y) - (a.y - o.y)*(b.x - o.x);
}
int inShape(Point &a, Point &b, Point &c, Point &t) {
    if(cross(a, b, t)*cross(a, c, t) > eps) {
        return 0;
    }
    if(cross(b, a, t)*cross(b, c, t) > eps) {
        return 0;
    }
    if(cross(c, a, t)*cross(c, b, t) > eps) {
        return 0;
    }
    return 1;
}
int main() {
    int n = 0, i;
    char s[1000];
    while(scanf("%s", s)) {
        if(s[0] == '*')
            break;
        if(s[0] == 'r') {
            scanf("%lf %lf %lf %lf %lf", &D[n].a.x, &D[n].a.y, &D[n].b.x, &D[n].b.y);
            D[n].sh = 1;
        } else if(s[0] == 'c') {
            scanf("%lf %lf %lf", &D[n].a.x, &D[n].a.y, &D[n].r);
            D[n].sh = 2;
        } else {
            scanf("%lf %lf %lf %lf %lf %lf", &D[n].a.x, &D[n].a.y, &D[n].b.x, &D[n].b.y, &D[n].c.x, &D[n].c.y);
            D[n].sh = 3;
        }
        n++;
    }
    int test = 0;
    double x, y;
    while(scanf("%lf %lf", &x, &y) == 2) {
        if(x == 9999.9 && y == 9999.9)
            break;
        test++;
        int flag = 0;
        for(i = 0; i < n; i++) {
            if(D[i].sh == 1) {
                if(D[i].a.x < x && x < D[i].b.x && D[i].a.y > y && y > D[i].b.y) {
                    printf("Point %d is contained in figure %d\n", test, i+1);
                    flag = 1;
                }
            } else if(D[i].sh == 2) {
                if((D[i].a.x-x)*(D[i].a.x-x)+(D[i].a.y-y)*(D[i].a.y-y) < D[i].r*D[i].r) {
                    printf("Point %d is contained in figure %d\n", test, i+1);
                    flag = 1;
                }
            } else {
                Point t;
                t.x = x, t.y = y;
                if(inShape(D[i].a, D[i].b, D[i].c, t)) {
                    printf("Point %d is contained in figure %d\n", test, i+1);
                    flag = 1;
                }
            }
        }
        if(!flag)
            printf("Point %d is not contained in any figure\n", test);
    }
    return 0;
}

478Points in FiguresRectanglesCirclesTriangles
台長:Morris
人氣(166) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][JAVA] 485 - Pascal's Triangle of Death
此分類上一篇:[UVA] 442 - Matrix Chain Multiplication

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文