[JAVA] 백준 12781 : PIZZA ALVOLOC

문제

12781번: PIZZA ALVOLOC

 

해결 방법

CCW (Counter-ColockWise) 라는 알고리즘을 쓰는 문제인데, 처음 보는 알고리즘이라 기록해둘 겸 글을 작성하게 되었다.

CCW는 '평면에 놓여진 세 점의 방향 관계를 구하는 알고리즘' 인데

 

CCW 식을 사용해서 양수가 나오면

이 그림과 같이 시계 반대 방향으로 향하는 방향 관계를 가지고 있다고 하고,

---

음수가 나온다면

이와 같이 시계 방향으로의 관계를 가지고 있다고 알 수 있다.

 

그러면 0이 나오는 경우는 뭘까?

그때는 세 점의 관계가 평행 즉, 일직선 상에 존재한다고 할 수 있다.

---

 

이 문제에서는 피자가 나눠 먹을 수 있게 4조각으로 나눠지기만 하면 된다고 하기 때문에

A, B, C, D 점이 존재한다고 할 때 A B C와 A B D는 서로 시계방향과 시계 반대방향으로 관계를 가지고 

B C A와 B C B 또한 서로 시계방향과 반대방향으로 관계를 가지고 있어야 한다.

그래야 서로 교차해서 4조각을 나눌 수 있다.

 

왜 A B C와 A B D만 CCW로 시계방향과 시계 반대방향인지 체크하면 안 되냐면

이 그림과 같은 경우 A B C와 A B D는 서로 시계 반대 방향과 시계 방향의 관계를 가지고 있지만 서로 교차를 하지 않은 것을 알 수 있다.

그래서 추가로 C D A와 C D B까지 CCW로 확인해서 시계 방향과 시계 반대 방향의 관계를 가지고 있는지 확인을 해야 한다.

 

CCW 식은 각 3개의 점의 좌표를 x와 y로 나타낼 수 있을 때

(x1 * y2 + x2 * y3 + x3 * y1) - (y1 * x2 + y2 * x3 + y3 * x1) 이다.

 

A B C와 A B D는 서로 시계방향과 시계 반대방향으로 관계를 가진다면 둘을 곱했을 때 -1 이 나올 것이고

B C A와 B C B 또한 -1이 나와야 한다. (1 * -1 = -1)

그래서 둘을 구한 결과 값인 a, b가 둘 다 음수 일 때 피자를 나눠먹을 수 있다.

 

코드는 다음과 같다.

 

코드

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

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());
		
		int a = ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4);
		int b = ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2);
		
		if (a < 0 && b < 0) System.out.println(1);
		else System.out.println(0);
		
	}
	
	static int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
		int cal = ((x1 * y2) + (x2 * y3) + (x3 * y1)) - ((y1 * x2) + (y2 * x3) + (y3 * x1));
		
		if (cal > 0) return 1;
		else if (cal == 0) return cal;
		return -1;
	}
}