477 - Points in Figures: Rectangles and Circles

Given a list of figures (rectangles and circles) 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(  ) figures descriptions, one per line. The first character will designate the type of figure (``r'', ``c'' for rectangle or circle, 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.

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

Diagrama of sample input figures and data points

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

---

問題敘述

這題是 476 - Points in Figures: Rectangles (Chinese version) 這一題的擴充，一樣是判斷點有沒有在圖形內，只不過多增加了圓形。

解題思路

如何判斷點有沒有在矩形內在上一題就已經說明過，所以不再贅述。至於如何判斷點有沒有在圓形內就是算出點和圓心之間的距離並且判斷此距離有沒有小於半徑即可。為了操作方便，程式裡用了點繼承的小技巧，來達到一樣是Figure但是長方形和圓形各有不同判斷點是否在圖形內的方法的效果。

c++ 程式碼

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

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

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

class Figure {
    public:
        virtual bool contain(Point*) = 0;
};

class Rectangle: public Figure {
    public:
        double x1, y1, x2, y2;
        Rectangle(double, double, double, double);
        bool contain(Point*);
};

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

bool Rectangle::contain(Point* point) {
    if (this->x1 < point->x && point->x < this->x2 && this->y1 > point->y && point->y > this->y2)
        return true;
    else
        return false;
}

class Circle: public Figure {
    public:
        double x, y, radius;
        Circle(double, double, double);
        bool contain(Point*);
};

Circle::Circle(double x, double y, double radius):x(x), y(y), radius(radius) {
}

bool Circle::contain(Point* point) {
    double dis = sqrt(pow(this->x - point->x, 2) + pow(this->y - point->y, 2));

    if (dis < radius)
        return true;
    else
        return false;
}

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

    while (true) {
        char sym;

        cin >> sym;
        if (sym == '*')
            break;
        else if (sym == 'r') {
            double x1, y1, x2, y2;
            Rectangle* rec;

            cin >> x1 >> y1 >> x2 >> y2;
            rec = new Rectangle(x1, y1, x2, y2);
            figVec.push_back(rec);
        }
        else {
            double x, y, radius;
            Circle* circle;

            cin >> x >> y >> radius;
            circle = new Circle(x, y, radius);
            figVec.push_back(circle);
        }
    }
    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]->contain(pointVec[i])) {
                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;
}