【解題】Points in Figures: Rectangles and Circles

ACM Volume IV 477 - Points in Figures: Rectangles and Circles


The Problem

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


解題思考

　　這題算是 476 的進階版(?)，所以我的解題方式基本上也大致相同。

　　些許不同的是，我將之前定義矩形的 struct "rectangle" 改成 "figure"，並加入兩個成員。其中一個用以代表圖形的類別(矩形或是圓形)，另一個則代表圓形的半徑(假如圖形是矩形則用不到)。

　　接著，同樣宣告出一個大小為 10 的 figure 結構陣列，再根據輸入資料依序將圖形資料存入陣列中。

　　判斷點在矩形中的方式，在 476 那題我已經做了解釋，在這裡不在贅述。

　　而點在圓形中的判斷法，就要用到圓形的平面座標方程式，也就是若點(X', Y')在圓心為(X, Y)的時候 [(X' - X)² + (Y' - Y)²]^1/2 < r 成立。由於開根號(A^1/2)結果較不精準，因此我們可以將之改寫成 (X' - X)² + (Y' - Y)² < r²。

　　最後，同樣照著題目要求輸出答案。這一題就解完了。


參考解答(C++)

#include <iostream>

using namespace std;

// 宣告圖形結構
struct figure
{
    char kind;
    double x1, x2, y1, y2, r;
};

int main(void)
{
    figure figs[10];

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

        if (c == '*')
        {
            size = i;
            break;
        }

        // 輸入是矩形
        else if (c == 'r')
        {
            cin >> figs[i].x1 >> figs[i].y1 >> figs[i].x2 >> figs[i].y2;
        }

        // 輸入是圓
        else if (c == 'c')
        {
            cin >> figs[i].x1 >> figs[i].y1 >> figs[i].r;
        }

        figs[i].kind = c;
    }

    // 點輸入迴圈
    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 (figs[j].kind == 'r')
            {
                if (x > figs[j].x1 && x < figs[j].x2 &&
                    y > figs[j].y2 && y < figs[j].y1)
                {
                    cout << "Point " << i << " is contained in figure " << j + 1 << endl;
                    contained = true;
                }
            }

            if (figs[j].kind == 'c')
            {
                double a = (x - figs[j].x1), b = (y - figs[j].y1);
                if (a * a + b * b < figs[j].r * figs[j].r)
                {
                    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
}