백준 1358 하키 Java: 직사각형과 두 원의 포함 관계

백준 1358번 ‘하키’의 경기장은 가운데 직사각형과 양옆의 반원으로 이루어진다. 선수 좌표가 직사각형 또는 왼쪽 원 또는 오른쪽 원 안에 있는지 확인하면 된다. 경계 위의 선수도 포함한다.

• 백준 1358번 하키

경기장을 세 영역의 합집합으로 보기

입력 W H X Y에서 직사각형의 왼쪽 아래가 아니라 문제 좌표계 기준 왼쪽 위가 (X, Y)이고, 범위는 다음과 같다.

X ≤ px ≤ X + W
Y ≤ py ≤ Y + H

양쪽 반원의 반지름은 H / 2이고 중심은 다음 두 점이다.

left center  = (X,     Y + H / 2)
right center = (X + W, Y + H / 2)

원 안에 있는지는 제곱 거리로 비교한다.

(px - cx)² + (py - cy)² ≤ radius²

반원만 따로 자르지 않고 원 전체를 검사해도 된다. 각 원에서 직사각형 쪽 절반은 이미 직사각형 영역과 겹치므로 세 영역의 합집합은 그대로 경기장 모양이 된다.

double 대신 정수 제곱 사용하기

원문은 Math.pow()와 double을 사용했다. 좌표와 반지름이 정수이고 제곱 비교만 하면 되므로 long 정수 연산이 더 간단하다. square root도 필요 없다.

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

public class Main {
    private static boolean isInsideCircle(
            int pointX,
            int pointY,
            int centerX,
            int centerY,
            int radius
    ) {
        long dx = (long) pointX - centerX;
        long dy = (long) pointY - centerY;
        return dx * dx + dy * dy <= (long) radius * radius;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int width = Integer.parseInt(tokenizer.nextToken());
        int height = Integer.parseInt(tokenizer.nextToken());
        int startX = Integer.parseInt(tokenizer.nextToken());
        int startY = Integer.parseInt(tokenizer.nextToken());
        int playerCount = Integer.parseInt(tokenizer.nextToken());

        int radius = height / 2;
        int centerY = startY + radius;
        int insideCount = 0;

        for (int player = 0; player < playerCount; player++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int pointX = Integer.parseInt(tokenizer.nextToken());
            int pointY = Integer.parseInt(tokenizer.nextToken());

            boolean insideRectangle = startX <= pointX
                    && pointX <= startX + width
                    && startY <= pointY
                    && pointY <= startY + height;
            boolean insideLeftCircle = isInsideCircle(
                    pointX, pointY, startX, centerY, radius
            );
            boolean insideRightCircle = isInsideCircle(
                    pointX, pointY, startX + width, centerY, radius
            );

            if (insideRectangle || insideLeftCircle || insideRightCircle) {
                insideCount++;
            }
        }

        System.out.println(insideCount);
    }
}

경계 조건

• 직사각형과 원의 경계도 경기장에 포함되므로 <가 아니라 ≤를 사용한다.
• 세 영역이 겹치는 점도 한 선수이므로 세 count를 더하지 않고 boolean OR로 한 번만 센다.
• 제곱하기 전 long으로 변환하면 좌표 범위가 커져도 int overflow를 피할 수 있다.

선수 수를 P라고 하면 각 좌표를 상수 번 비교하므로 시간 복잡도는 O(P), 추가 공간은 O(1)이다.

기하 단계에서 남긴 기록

원문에서는 직전에 풀었던 백준 1004 어린왕자와 마찬가지로 원의 방정식과 두 점 사이 거리로 바로 접근했다. 당시에는 “기하는 아느냐 모르느냐의 문제”라고 적고 곧바로 code로 들어갔고, 이 문제로 단계별 기하 section을 끝냈다고 기록했다.

지금 다시 보면 공식을 아는 것만큼 도형을 합집합과 포함 조건으로 번역하는 과정이 중요하다. 직사각형, 왼쪽 원, 오른쪽 원을 각각 작은 predicate로 나누면 그림의 방향보다 boundary rule을 code에서 확인하기 쉬워진다.

검증 범위

Java source를 수동 검토하고 직사각형 내부·두 원의 바깥쪽 끝·세 영역의 경계·완전한 외부 좌표를 독립 geometry predicate와 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.