SWEA 21426. 흰 종이와 검은 종이

(0, 0)에서 (10^6, 10^6) 까지의 좌표를 가진 테이블에 왼쪽 아래 좌표와 오른쪽 위 좌표가 주어진 직사각형 형태의 종이들을 놓는다. 흰 종이를 먼저 놓고 검은 종이 2개를 순서대로 놓을 때, 흰 종이가 보일 경우 YES, 아니면 NO를 출력하는 문제이다.

 

겹치는 영역 좌표는 두 영역의 좌하단의 최댓값, 우상단의 최솟값 좌표가 된다. 영역의 넓이를 계산할 때 높이, 깊이 둘 중 0 이하가 되는 부분이 있으면 겹치지 않는 것이므로 0으로 처리한다.

private static long[] intersectArea(long[] r1, long[] r2) {
    long x1 = Math.max(r1[0], r2[0]);
    long y1 = Math.max(r1[1], r2[1]);
    long x2 = Math.min(r1[2], r2[2]);
    long y2 = Math.min(r1[3], r2[3]);
    return new long[] { x1, y1, x2, y2 };
	}

private static long calculateArea(long[] r) {
    long width = Math.max(0, r[2] - r[0]);
    long height = Math.max(0, r[3] - r[1]);
    return width * height;
}

 

 

이후, 흰종이의 영역의 넓이를 구한 후, 검은 종이들과 겹치는 부분의 영역의 넓이를 구하여 빼준다. 세 종이 모두 겹칠 경우도 있기 때문에 모두 겹치는 영역의 넓이를 최종 결과에 더해주어야 한다.

long x1 = Long.parseLong(st.nextToken()), y1 = Long.parseLong(st.nextToken());
long x2 = Long.parseLong(st.nextToken()), y2 = Long.parseLong(st.nextToken());
long[] whitePoints = { x1, y1, x2, y2 };

st = new StringTokenizer(br.readLine());
long x3 = Long.parseLong(st.nextToken()), y3 = Long.parseLong(st.nextToken());
long x4 = Long.parseLong(st.nextToken()), y4 = Long.parseLong(st.nextToken());
long[] firstBlackPoints = { x3, y3, x4, y4 };

st = new StringTokenizer(br.readLine());
long x5 = Long.parseLong(st.nextToken()), y5 = Long.parseLong(st.nextToken());
long x6 = Long.parseLong(st.nextToken()), y6 = Long.parseLong(st.nextToken());
long[] secondBlackPoints = { x5, y5, x6, y6 };

long whiteArea = calculateArea(whitePoints);
long firstBlackArea = calculateArea(intersectArea(whitePoints, firstBlackPoints));
long secondBlackArea = calculateArea(intersectArea(whitePoints, secondBlackPoints));
long overlapBlackArea = calculateArea(intersectArea(firstBlackPoints,intersectArea(whitePoints, secondBlackPoints)));
if (whiteArea - firstBlackArea - secondBlackArea + overlapBlackArea > 0) {
    sb.append("YES");
} else {
    sb.append("NO");
}

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while (tc-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long x1 = Long.parseLong(st.nextToken()), y1 = Long.parseLong(st.nextToken());
            long x2 = Long.parseLong(st.nextToken()), y2 = Long.parseLong(st.nextToken());
            long[] whitePoints = { x1, y1, x2, y2 };

            st = new StringTokenizer(br.readLine());
            long x3 = Long.parseLong(st.nextToken()), y3 = Long.parseLong(st.nextToken());
            long x4 = Long.parseLong(st.nextToken()), y4 = Long.parseLong(st.nextToken());
            long[] firstBlackPoints = { x3, y3, x4, y4 };

            st = new StringTokenizer(br.readLine());
            long x5 = Long.parseLong(st.nextToken()), y5 = Long.parseLong(st.nextToken());
            long x6 = Long.parseLong(st.nextToken()), y6 = Long.parseLong(st.nextToken());
            long[] secondBlackPoints = { x5, y5, x6, y6 };

            long whiteArea = calculateArea(whitePoints);
            long firstBlackArea = calculateArea(intersectArea(whitePoints, firstBlackPoints));
            long secondBlackArea = calculateArea(intersectArea(whitePoints, secondBlackPoints));
            long overlapBlackArea = calculateArea(intersectArea(firstBlackPoints, intersectArea(whitePoints, secondBlackPoints)));
            if (whiteArea - firstBlackArea - secondBlackArea + overlapBlackArea > 0) {
                sb.append("YES");
            } else {
                sb.append("NO");
            }
            sb.append('\n');
        }
        br.close();
        System.out.print(sb);
    }

    private static long[] intersectArea(long[] r1, long[] r2) {
        long x1 = Math.max(r1[0], r2[0]);
        long y1 = Math.max(r1[1], r2[1]);
        long x2 = Math.min(r1[2], r2[2]);
        long y2 = Math.min(r1[3], r2[3]);
        return new long[] { x1, y1, x2, y2 };
    }

    private static long calculateArea(long[] r) {
        long width = Math.max(0, r[2] - r[0]);
        long height = Math.max(0, r[3] - r[1]);
        return width * height;
    }
}