12781 - PIZZA ALVOLOC
문제 풀이 시간 : 1시간
문제 설명:
- •
도윤이는 친구 3명과 함께 피자를 나눠 먹는다.
- •
피자는 항상 볼록 다각형이다.
- •
피자를 네등분해서 나눠 먹는다.
- ◦
한 명씩 피자의 가장자리 한 점을 선택한다.
- ◦
선택한 순서대로 1, 2번 점을 이어 선분을 만들고, 3, 4번 점을 이어 선분을 만든다.
- ◦
만들어진 두 선분을 따라 피자를 자른다.
- •
나누어진 피자가 4조각이 되는지 판단하자.
문제 풀이:
이 문제는 저번 시간에 발표했던 CCW를 활용하는 문제이다.
이왕 CCW를 알아본 김에 활용문제를 좀 풀어보면서 어떤식으로 쓰이는지 알아보고자 풀게되었다.
다들 CCW의 공식은 기억하겠지..?
나는 처음 이 문제를 보자마자 아래와 같이 두 점을 기준으로 나머지 두 점과의 위치 관계를 CCW로 판단하여
두 선의 방향이 반대라면 4조각으로 나누어지는 것이 아닌가? 라는 생각으로 문제를 풀었다.
코드
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를 이용해서 선분의 교차 여부를 판단하고자 한다면 다른 두 점을 사용해서 모든 경우를 판단해봐야 한다고 한다.
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);
}
}