476 - Points in Figures: Rectangles

🌕🌑🌑🌑🌑

# 題目連結

• 題目連結
• Online Judge
• uDebug

# 題目說明

Time limit: 3.000 seconds

# 題目

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.

Note: See the picture on the right for a diagram of these figures and data points.

# 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

# 解題技巧

這題難點是要怎麼處理跟儲存資料，至於判斷 (x, y) 是否在某個 figure 中，可以利用 (x, y) 是否介於該 figure 中。

# Solution

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String c = sc.next();

        Map<Integer, double[][]> figure = new HashMap<>();

        int figureCount = 0;

        while (!c.equals("*")) {

            double[][] f = new double[2][2];

            figureCount++;

            f[0][0] = sc.nextDouble();

            f[1][1] = sc.nextDouble();

            f[0][1] = sc.nextDouble();

            f[1][0] = sc.nextDouble();

            figure.put(figureCount, f);

            c = sc.next();

        }

        int pointCount = 0;

        double x = sc.nextDouble();

        double y = sc.nextDouble();

        while (x != 9999.9 && y != 9999.9) {

            boolean check = false;

            pointCount++;

            for (int key : figure.keySet()) {

                double[][] f = figure.get(key);

                if (f[0][0] < x && f[0][1] > x && f[1][0] < y && f[1][1] > y) {

                    System.out.println("Point " + pointCount + " is contained in figure " + key);

                    check = true;

                }

            }

            if (!check) {

                System.out.println("Point " + pointCount + " is not contained in any figure");

            }

            x = sc.nextDouble();

            y = sc.nextDouble();

        }

    }

}