476 - Points in Figures: Rectangles

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(  ) 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

出處: UVa Online Judge - Points in Figures: Rectangles

---

問題敘述

此題會先輸入很多行長方形座標資料，每行的開頭為 r 代表長方形，接著會輸入四個浮點數，前兩個浮點數代表此長方形左上角的座標，後兩個浮點數代表此長方形右下角的座標，長方形資料一直輸入到出現 * 就結束。接著會輸入很多行成對的浮點數，每對各代表一個點座標，您的任務是要求出這些點各被包含在哪些長方形裡面。

解題思路

因為矩形的輸入資料只給出左上角的座標(設: x1, y1)以及右下角的座標(設: x2, y2)，所以可以知道 x1 <= x2 和 y1 >= y2。若點(設 x, y)要落在矩形裡勢必要符合此條件: x1 < x < x2 and y1 > y > y2(沒有等於，因為落在邊上不算被包含在裡面)，依照此規則就可以判斷點是否落在矩形內。

c++ 程式碼

#include <iostream>
#include <vector>
using namespace std;

class Figure {
    public:
        double x1, y1, x2, y2;
        Figure(double, double, double, double);
};

Figure::Figure(double x1, double y1, double x2, double y2):x1(x1), y1(y1), x2(x2), y2(y2) {
}

class Point {
    public:
        double x, y;
        Point(double, double);
};

Point::Point(double x, double y):x(x), y(y) {
}

int main() {
    vector<Figure*> figVec;
    vector<Point*> pointVec;

    while (true) {
        char sym;
        double x1, y1, x2, y2;
        Figure* fig;

        cin >> sym;
        if (sym == '*')
            break;
        cin >> x1 >> y1 >> x2 >> y2;
        fig = new Figure(x1, y1, x2, y2);
        figVec.push_back(fig);
    }
    while (true) {
        double x, y;
        Point* point;

        cin >> x >> y;
        if (x == 9999.9 && y == 9999.9)
            break;
        point = new Point(x, y);
        pointVec.push_back(point);
    }
    for (int i=0; i<pointVec.size(); i++) {
        bool isContained = false;

        for (int j=0; j<figVec.size(); j++) {
            if (figVec[j]->x1 < pointVec[i]->x && pointVec[i]->x < figVec[j]->x2 &&
                    figVec[j]->y1 > pointVec[i]->y && pointVec[i]->y > figVec[j]->y2) {
                cout << "Point " << i + 1 << " is contained in figure " << j + 1 << endl;
                isContained = true;
            }
        }
        if (!isContained)
            cout << "Point " << i + 1 << " is not contained in any figure" << endl;
    }
    for (int i=0; i<figVec.size(); i++)
        delete figVec[i];
    for (int i=0; i<pointVec.size(); i++)
        delete pointVec[i];

    return 0;
}