【解題】Points in Figures: Rectangles

ACM Volume IV 476 - Points in Figures: Rectangles


The Problem

Given a list of rectangles 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) rectangles descriptions, one per line. The first character will designate the type of figure (``r'' for rectangle). This character will be followed by four real values designating the x-y coordinates of the upper left and lower right corners.

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
r 0.0 10.3 5.5 0.0
r 2.5 12.5 12.5 2.5
*
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 2
Point 2 is contained in figure 2
Point 2 is contained in figure 3
Point 3 is contained in figure 3
Point 4 is not contained in any figure
Point 5 is contained in figure 1
Point 6 is not contained in any figure


Diagrama of sample input figures and data points


解題思考

　　這題我的方式，就是先定義出一個矩形的結構(struct) "rectangle"。接著，宣告出一個大小為 10 (因為題目給定的 n 是大於等於 10 的)的 rectangle 結構陣列。之後再根據輸入資料依序將矩形資料存入陣列中。

　　之後就是如何判斷點在矩形中了。其實判斷的原理相當簡單，就是點的 x 座標介於矩形的兩個 x 座標之間，且點的 y 座標介於矩形的兩個 y 座標之間。接著再根據題目要求輸出判斷結果，這題就解完了。


參考解答(C++)

#include <iostream>

using namespace std;

// 宣告矩形結構
struct rectangle
{
    double x1, x2, y1, y2;
};

int main(void)
{
    rectangle rects[10];

    // 圖形輸入迴圈
    int size;
    for (int i = 0; ; i++)
    {
        char c;
        cin >> c;

        if (c == '*')
        {
            size = i;
            break;
        }
        else if (c == 'r')
        {
            cin >> rects[i].x1 >> rects[i].y1 >> rects[i].x2 >> rects[i].y2;
        }
    }

    // 點輸入迴圈
    for (int i = 1; ; i++)
    {
        double x, y;
        bool contained = false;

        cin >> x >> y;

        if (x == 9999.9 && y == 9999.9) { break; }

        // 判別點在哪個圖形中
        for (int j = 0; j < size; j++)
        {
            if (x > rects[j].x1 && x < rects[j].x2 &&
                y > rects[j].y2 && y < rects[j].y1)
            {
                cout << "Point " << i << " is contained in figure " << j + 1 << endl;
                contained = true;
            }
        }

        // 假如不在任何圖形中
        if (!contained)
        {
            cout << "Point " << i << " is not contained in any figure" << endl;
        }
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}