백준 12781 - PIZZA ALVOLOC 자바 풀이

문제 링크

문제 풀이 시간 : 1시간

문제 설명:

도윤이는 친구 3명과 함께 피자를 나눠 먹는다.
피자는 항상 볼록 다각형이다.
피자를 네등분해서 나눠 먹는다.
나누어진 피자가 4조각이 되는지 판단하자.

문제 풀이:

이 문제는 저번 시간에 발표했던 CCW를 활용하는 문제이다.

이왕 CCW를 알아본 김에 활용문제를 좀 풀어보면서 어떤식으로 쓰이는지 알아보고자 풀게되었다.

다들 CCW의 공식은 기억하겠지..?

나는 처음 이 문제를 보자마자 아래와 같이 두 점을 기준으로 나머지 두 점과의 위치 관계를 CCW로 판단하여

두 선의 방향이 반대라면 4조각으로 나누어지는 것이 아닌가? 라는 생각으로 문제를 풀었다.

코드

java

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

public class Main {
    public static class Point {
        private final int a, b;

        Point(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Point[] arr = new Point[5];
        Point[] arr1 = new Point[4];
        Point[] arr2 = new Point[4];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            arr[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        for (int i = 0; i < 2; i++) {
            arr1[i] = arr2[i] = arr[i];
        }
        arr1[2] = arr[2];
        arr2[2] = arr[3];
        arr1[3] = arr2[3] = arr[0];
        int d1 = 0, d2 = 0;
        for (int i = 0; i < 3; i++) {
            d1 += arr1[i].a * arr1[i + 1].b;
            d2 += arr2[i].a * arr2[i + 1].b;
        }
        for (int i = 1; i <= 3; i++) {
            d1 -= arr1[i].a * arr1[i - 1].b;
            d2 -= arr2[i].a * arr2[i - 1].b;
        }

        if (d1 * d2 < 0) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
}

위와 같이 코드를 짰더니 1%에서 틀렸다가 나온다.

왜 그럴까?

아무리 생각해도 문제점이 보이지 않았다.

그래서 결국 검색 찬스를 쓰게 되었다.

나는 그냥 예시 사진만 보고 정다각형이라고 생각한 것이다.

근데 문제에서는 볼록 다각형이라고 주어졌다.

즉, 피자의 모양은 얼마든지 기괴해질 수 있다는 것이다.

아래와 같은 상황을 보자.

실제로는 이런 상황은 없겠지만 극단적인 예이다.

위의 예시를 봤을 때, A,B를 기준으로 C,D를 판단했을 때는 두 선이 반대 방향이므로 CCW를 만족하는 것처럼 보인다.

하지만, C,D를 기준으로 A,B를 본다면 두 선이 같은 방향이 된다.

따라서 이 4점은 교차하지 않는다는 것을 알 수 있다.

이렇게 CCW를 이용해서 선분의 교차 여부를 판단하고자 한다면 다른 두 점을 사용해서 모든 경우를 판단해봐야 한다고 한다.

java

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

public class Main {
    public static class Point {
        private final int a, b;

        Point(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    public static int ccw(Point p1, Point p2, Point p3) {
        int d = p1.a * p2.b + p2.a * p3.b + p3.a * p1.b;
        d -= p2.a * p1.b + p3.a * p2.b + p1.a * p3.b;

        if (d > 0) return 1;
        else if (d < 0) return -1;
        else return 0;
    }

    public static boolean isPossible(int d1, int d2) {
        return d1 * d2 < 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Point[] arr = new Point[4];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            arr[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        if (isPossible(ccw(arr[0], arr[1], arr[2]), ccw(arr[0], arr[1], arr[3]))) {
            if (isPossible(ccw(arr[2], arr[3], arr[0]), ccw(arr[2], arr[3], arr[1]))) {
                System.out.println(1);
                return;
            }
        }
        System.out.println(0);
    }
}

12781 - PIZZA ALVOLOC

문제 풀이 시간 : 1시간

문제 설명:

문제 풀이:

코드

함께 읽으면 좋은 글

5430번 - AC

1966번 - 프린터 큐

1158 - 요세푸스 문제

2164번 - 카드2