Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

32. 기하

조금 더 어려운 기하 문제를 풀어 봅시다.

Java / Python

2. CCW

11758번

세 점이 이루는 방향을 구하는 문제

이번 문제는 2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하는 문제이다.

기하 알고리즘을 공부한다면 필수적으로 알아야 하는 기하학의 기초 알고리즘인 CCW 입문 문제이다. CCW는 Counter Clockwise의 약자로, 평면 위 놓여진 세 점의 방향 관계를 구할 수 있는 알고리즘이다. CCW는 점 A, B, C를 순서대로 볼 때, 반시계 방향으로 놓여 있으면 양수, 시계 방향이면 음수, 평행하게 놓여있으면 0을 반환한다. 신발끈 공식을 사용한다.

• Java

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

public class Main {
	static class Point {
		int x, y;

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

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		Point[] point = new Point[3];

		for (int i = 0; i < 3; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			point[i] = new Point(x, y);
		}

		bw.write(ccw(point) + "\n");

		bw.flush();
		bw.close();
		br.close();
	}

	public static int ccw(Point[] p) {
		// CCW 공식 (x1y2+x2y3+x3y1)−(y1x2+y2x3+y3x1)
		int result = ((p[0].x * p[1].y) + (p[1].x * p[2].y) + (p[2].x * p[0].y))
				- ((p[0].y * p[1].x) + (p[1].y * p[2].x) + (p[2].y * p[0].x));
		if (result > 0)
			return 1;
		else if (result == 0)
			return 0;
		else
			return -1;
	}
}

• Python

import sys
input = sys.stdin.readline
point = []
for _ in range(3):
    point.append(list(map(int, input().split())))
    
def ccw(p1, p2, p3):
    return (p1[0]*p2[1] + p2[0]*p3[1] + p3[0]*p1[1]) - (p2[0]*p1[1] + p3[0]*p2[1] + p1[0]*p3[1])

result = ccw(point[0], point[1], point[2])
if result > 0:
    print(1)
elif result == 0:
    print(0)
else:
    print(-1)