[KOITP] 점의 위치

출    처 : http://koitp.org/problem/SDS_PRO_9_2/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	1267	218 (17%)	176

문제

이차원 평면에서 점 N개로 이루어진 다각형이 주어진다.

그리고 평면위의 점 P1, P2가 주어졌을때 점 P1, P2가 다각형의 외부에 있는지, 내부에 있는지 판별하는 프로그램을 작성하시오.

점 P1, P2 는 주어진 다각형의 선분 위에 존재하지는 않는다.

입력

첫째 줄에 다각형을 이루는 점의 갯수 (1 ≦ N ≦ 100,000)이 주어지고,

둘째 줄 부터 N개의 점의 정수 좌표(-10^9 ≦ x, y ≦ 10^9)가 입력으로 주어진다.

다각형의 좌표는 시계 방향 또는 반시계 방향 순서로 주어진다.

마지막 두 줄에는 점 P1, p2 의 좌표가 주어진다.

출력

첫째 줄에는 점 P1가 주어진 다각형 안에 존재한다면 "in", 밖에 존재한다면 "out"을 출력한다.

둘째 줄에는 점 P2가 주어진 다각형 안에 존재한다면 "in", 밖에 존재한다면 "out"을 출력한다.

힌트

입력 예시

4
1 1
1 3
3 3
3 1
0 0
2 2

출력 예시

out
in

< Comment >

 처음에는 전부 다 외적을 구해가면서 계산하려고 했었는데, 조금 코드를 짜기 난해했고, 아마 짰더라도 시간초과가 발생하지 않았을까 싶습니다. 기본적으로 컨셉은 간단하지만 굉장히 효율적입니다. 점이 안에 있는지 밖에 있는지 판별하는 것은 판별하고자 하는 점과 반드시 다각형의 바깥쪽에 위치하는 점을 선분으로 이었을때, 교점이 짝수개이면 바깥쪽이고, 안쪽이면 홀수개가 됩니다.

 여기서 주어지는 점들의 범위가 10^9 이므로, 이 밖에 지점을 원소로 잡습니다. y축의 경우 1로 넣은 이유는, 좌표가 정수로 주어지기 때문에 1을 더하게 되면 해당 선분은 양 끝점을 제외하고 절대로 정수좌표를 선분 내에 포함하지 않기 때문입니다. 우선 점이 또 다각형 위에 있지는 않다고 주어졌기 때문에, 이를 가지고 몇가지 함수를 만들었습니다.

 ccw 함수는 두 점 a와 b를 이은 선분에 대해서 점 c가 반시계방향(ccw) 에 있으면 1을 시계방향 쪽(cw) 에 있으면 -1을 직선상에 있으면 0을 리턴하도록 만들어두었고, 이를 기반으로 a와 b를 잇는 선분과 c와 d를 잇는 선분의 교차횟수를 카운트하여 결과를 출력하도록 만들었습니다. 기본적으로 두 선분이 교차하려면 각각 선분이 다른 선분의 두 점에 대하여, 하나는 cw 하나는 ccw여야 교차하기 때문에, 해당 경우를 판별하고, 교차하지 않았을 경우의 false 값에서 교차할 때마다 값을 Toggle 해주어 결과를 출력하도록 만들었습니다. 해당 연산자는 사실 java를 쓸 때는 거의 처음 써보는 것 같은데, 유용할 것 같아 한 번 사용해 보았습니다. ^= 는 일반적으로 말하는 XOR입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class PointPosition {

	public static class Point {
		
		long x = 0;
		long y = 0;
		
		public Point (long x, long y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static int N = 0;
	public static Point[] points = null;
	
	public static Point P1 = null;
	public static Point P2 = null;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		points = new Point[N];
		
		
		StringTokenizer st = null;
		long x = 0;
		long y = 0;
		for (int i = 0 ; i < N + 2 ; i++) {		// 시계방향으로 주어지는 값들
			
			st = new StringTokenizer(br.readLine());
			x = Long.parseLong(st.nextToken());
			y = Long.parseLong(st.nextToken());
			
			if (i < N) {
				points[i] = new Point(x, y);
			} else {
				
				if (i == N) {
					P1 = new Point(x, y);
				} else {
					P2 = new Point(x, y);
				}
			}
		}
		
		bw.write(isInside(P1) ? "in\n" : "out\n");
		bw.write(isInside(P2) ? "in\n" : "out\n");
		bw.flush();
		bw.close();
	}
	
	public static boolean isInside (Point p) {
		
		Point farP = new Point((long)1e9 + 1, p.y + 1);
		
		boolean ret = false;
		for (int i = 0 ; i < N ; i++) {
			
			int j = (i + 1) % N;
			if (isCross(p, farP, points[i], points[j])) {
				ret ^= true;			// XOR
			}
		}
		
		return ret;
	}
	
	public static boolean isCross (Point a, Point b, Point c, Point d) {
		// 교차할 경우 c와 d의 위치는 ab 를 기준으로 하나는 cw 하나는 ccw일 것이기 때문
		boolean ret = (ccw(a, b, c) * ccw(a, b, d) < 0) && (ccw(c, d, a) * ccw(c, d, b) < 0) ? true : false;
		return ret;
	}
	
	public static long ccw (Point a, Point b, Point c) {
		
		long outPd = outerProduct(new Point(b.x - a.x, b.y - a.y), new Point(c.x - a.x, c.y - a.y));
		if (outPd > 0)	return 1;		// CCW
		if (outPd < 0)	return -1;		// CW
		else			return 0;		// On Line
	}
	
	public static long outerProduct (Point a, Point b) {
		long ret = (a.x * b.y) - (a.y * b.x);
		return ret;
	}
}