[백준] 12781번 - PIZZA ALVOLOC [Java]

https://www.acmicpc.net/problem/12781

 

[백준] 12781번 - PIZZA ALVOLOC [Java]

[백준] 12781번 - PIZZA ALVOLOC [Java]

---

1.  아이디어

 

피자를 네 조각으로 나누려면 두 선분이 서로 교차해야한다는 점에서 선분 교차 유형임을 파악하고 CCW 알고리즘을 활용해서 사이 좋게 피자를 나누어 먹을 수 있는지 파악했다.

---

2. 문제풀이

 

네 점을 A, B, C, D 순서라고 할 때 선분 AC와 선분 BD가 만들어진다.

여기서 선분 교차 판정을 하면 되는데 선분 AC에 대해 두 점이 선분의 반대쪽에 있어야 하고, 선분 BD에 대해 두 점이 선분의 반대쪽에 있어야 한다.

이를 CCW에 적용하면 벡터 AC와 벡터 AB의 외적, 벡터 AC와 벡터 AD의 외적, 두 외적 벡터의 방향이 반대여야하고, 벡터 BD와 벡터 BA의 외적, 벡터 BD와 벡터 BC의 외적, 두 외적 벡터의 방향이 반대여야한다.

 

점의 좌표는 절댓값 10,000 이내지만 CCW 이후 판단 과정에서 int형의 범위를 넘을 수 있어서 long 타입 변환을 적절히 활용했다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int x1 = Integer.parseInt(st.nextToken());
        int y1 = Integer.parseInt(st.nextToken());
        int x2 = Integer.parseInt(st.nextToken());
        int y2 = Integer.parseInt(st.nextToken());
        int x3 = Integer.parseInt(st.nextToken());
        int y3 = Integer.parseInt(st.nextToken());
        int x4 = Integer.parseInt(st.nextToken());
        int y4 = Integer.parseInt(st.nextToken());

        if (ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) < 0 &&
                ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) < 0) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }

    private static long ccw(long x1, long y1, long x2, long y2, long x3, long y3) {
        return (x1 * y2 - x2 * y1) + (x2 * y3 - x3 * y2) + (x3 * y1 - x1 * y3);
    }

}

---

4. 후기