[백준 13352] 석양이 진다...

CCW 문제

www.acmicpc.net/problem/13352

 

www.acmicpc.net/problem/11758

CCW에 대해 모른다면 위 문제를 먼저 푸는 것을 권장합니다.

---

[문제 풀이]

 

N개의 점들이 주어졌을 때 점들이 두 개 이하의 직선을 이루는지 판별하는 문제입니다.

 

이 문제가 어렵게 느껴지는 이유는 어떻게 점들을 두 직선에 넣는지에 대한 생각이 어렵기 때문입니다.

점을 기준으로 생각한다면 모든 점을 탐색하면서 직선이 두 개 이하로 나오는지 검사하는 방법 말고는 떠오르지 않습니다.

그리고 단순히 완전 탐색을 하려 한다면 N의 최대 제한이 100이어도 통과하기 어려워 보입니다.

 

그렇다면 점이 아닌 직선을 기준으로 생각해봅시다.

두 직선을 만들어 놓고 점들이 직선에 포함되는지 확인만 한다면, 상당히 빠르게 답을 구할 수 있을 것 같습니다.

 

 

직선을 기준으로 설명해야 하므로 편의를 위해서 지금부터 표현할 두 직선을 직선A, 직선B라고 작성합니다.

 

이 문제의 핵심 아이디어는 우선 직선A를 구성하는 것입니다.

우선 직선A을 만들고 난 뒤, 나머지 점들이 직선A에 포함되는 경우 직선A로, 그렇지 않은 경우는 직선B로 넣어버리고 직선B마저 들어가지 못한다면 failure를 출력하면 됩니다.

=> 문제를 해결하는 로직

 

그렇다면 직선A를 구성해야 하는데 그냥 점 두 개를 임의로 고르고 직선을 구성한 후에 나머지를 위의 아이디어대로 풀이를 하면 또 다른 완전 탐색이 됩니다.

직선을 기준으로 생각하기로 했지만 두 개의 점만으로 구성한 직선이 충분한 기준이 안 되어 계속 직선을 변경할 수 있기 때문입니다.

 

즉, 우리는 직선A를 구성하는 데에 그치지 말고, 직선A를 확정 지어야 합니다.

직선을 확정 짓는 방법은 생각보다 단순합니다.

두 개의 점으로 직선을 만드는 것이 아닌, 세 점으로 직선을 구성한다면 하나의 직선이 확정됩니다.

 

세 점으로 직선을 구성하는 방법, 즉 CCW를 사용하여 그 결과가 0인 세 점을 기준으로 잡고 직선A를 확정 지으면 모든 준비가 끝났습니다.

 

하지만 점들의 집합에서 CCW가 0이 되는 세 점을 뽑는 시간 복잡도는 O(n^3)이므로 모든 점에 대해서 세 점을 뽑는 검사를 실행한다면 시간 초과가 발생합니다.

즉, 최소한의 점들만 확인하여 세 점을 확인할 수 있다면, 이제 이 문제는 해결이 가능합니다.

 

최소한의 점의 개수는 비둘기집 원리로 해결 가능합니다. 

 

점이 네 개인 경우

위 그림처럼 점이 네 개인 경우 직선을 어떻게 그어도 두 직선에 포함된다는 것을 확인할 수 있습니다.

즉 비둘기집이 가득찬 상태라고 생각할 수 있습니다.

두 개의 점만으로 직선이 확정되지 않음을 보여주는 예시이기도 합니다.

 

하지만 다섯 개의 점으로 생각한다면 확정이 되지 않은 두 개의 직선과 하나의 점이 남게 됩니다.

비둘기집 원리에 의해 다섯 개의 점부터는 남은 하나의 점으로 무조건 직선이 확정되던지, failure를 출력할 것인지 알 수 있게 됩니다.

이제 이 하나의 점이 이미 만들어졌던 두 직선 중 하나에 포함되는지 확인하는 과정에서 직선의 확정 혹은 failure를 출력할지 결정하고, 이 과정을 간략화하여 세 개의 점으로 CCW가 0이 되는지 확인했던 것입니다.

 

위의 과정을 통해 최소 다섯 개의 점만 확인하여도 직선A를 확정시키거나, failure를 출력함을 확인할 수 있습니다.

만약 직선A가 확정됐다면 남은 모든 점을 확인하면서 위의 로직을 수행하면 되므로 O(n)만큼의 시간이 소요됩니다.

 

직선A를 확정시키는 것은 5^3만큼 반복하고, 위에서 설명한 로직은 O(n)이 걸리므로 5초 안에 충분히 통과가 가능합니다.

 

---

[소스 코드] / JAVA

 

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

public class Main {
	static ArrayList<Point> Firstshot = new ArrayList<>();
	static ArrayList<Point> Secondshot = new ArrayList<>();
	static Point[] enemy;

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

		int N = Integer.parseInt(br.readLine());
		enemy = new Point[N];

		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			long x = Long.parseLong(st.nextToken());
			long y = Long.parseLong(st.nextToken());
			enemy[i] = new Point(x, y);
		}

		System.out.println(shot(N));
	}

	private static String shot(int N) {
		if (N > 4) {
			ready2Roll();
			if (Firstshot.isEmpty())
				return "failure";
			else {
				for (int i = 5; i < N; i++) {
					if (CCW(Firstshot.get(0), Firstshot.get(1), enemy[i])) {
						continue;
					}
					if (Secondshot.size() < 2) {
						Secondshot.add(enemy[i]);
						continue;
					} else {
						if (CCW(Secondshot.get(0), Secondshot.get(1), enemy[i])) {
							continue;
						}
					}
					return "failure";
				}
			}

		}
		return "success";
	}

	private static void ready2Roll() {
		boolean[] visited = new boolean[5];
		boolean flag = false;

		for (int i = 0; i < 3; i++) {
			for (int j = i + 1; j < 4; j++) {
				for (int k = j + 1; k < 5; k++) {
					if (CCW(enemy[i], enemy[j], enemy[k])) {
						Firstshot.add(enemy[i]);
						Firstshot.add(enemy[j]);
						Firstshot.add(enemy[k]);
						
						visited[i] = visited[j] = visited[k] = true;
						flag = true;
						
						break;
					}
				}
				if (flag) break;
			}
			if (flag) break;
		}

		if (!Firstshot.isEmpty()) {
			for (int i = 0; i < 5; i++) {
				if (!visited[i] && !CCW(Firstshot.get(0), Firstshot.get(1), enemy[i])) {
					Secondshot.add(enemy[i]);
				}
			}
		}

	}

	private static boolean CCW(Point p1, Point p2, Point p3) {
		long S = p1.x * p2.y + p2.x * p3.y + p3.x * p1.y;
		S -= p1.y * p2.x + p2.y * p3.x + p3.y * p1.x;
		if (S == 0) return true;
		return false;
	}

	private static class Point {
		long x, y;

		public Point(long x, long y) {
			this.x = x;
			this.y = y;
		}
	}
}