백준 11758 (CCW)

백준 11758 (CCW)

문제 링크

문제 링크 : https://www.acmicpc.net/problem/11758

문제 접근

세 점이 주어졌을 때, 세 점을 연결한 선분의 방향이 시계 방향(clockwise)인지, 반시계 방향(counter clockwise)인지 판단하는 문제입니다. 저번 학기 컴퓨터 알고리즘 시간에 기하학 알고리즘(geometry algorithm)에 간략하게 배웠던 것이 생각나네요.

ccw인지, cw인지 판단하는 방법은 1) 세 점 (p1 , p2, p3)으로, 두 벡터(p1p2 , p2p3)를 만들고 2) 두 벡터의 외적(cross product)를 구하고 3) 외적의 크기가 0이라면 일직선, 0보다 크다면 반시계, 0보다 작다면 시계 방향으로 판단합니다.

왜냐하면 외적은 두 벡터의 시점을 일치시킨 후, 하나의 벡터를 기준으로 오른손 법칙을 사용해서 구할 수 있기 때문입니다.

이 문제는, 2차원 좌표계는 3차원 좌표계에서 z=0인 어떤 “매우 특수한” 평면으로 볼 수가 있습니다. (z좌표를 통일시키기만 한다면 해결 가능합니다.)

x2 - x1	y2 - y1	0
x3 - x2	y3 - y2	0
0	0	0

행렬의 행렬식은 x1y2 + x2y3 + x3y1 - (x1y3 + x3y2 + x2y1)이므로, 이의 부호가 0보다 작다면 시계 방향, 0보다 크다면 반시계 방향, 0이라면 두 벡터는 평행하고 하나의 종점이 나머지 벡터의 시점이 되므로, 직선으로 판단할 수 있습니다.

소스 코드

import sys
def cross_product(p1,p2,p3) :
	x1=p1[0]
	x2=p2[0]
	x3=p3[0]
	y1=p1[1]
	y2=p2[1]
	y3=p3[1]
	return x1*y2 + x2*y3 + x3*y1 - (x1*y3 + x3*y2 + x2*y1)

p1 =  list(map(int,sys.stdin.readline().split()))
p2 =  list(map(int,sys.stdin.readline().split()))
p3 =  list(map(int,sys.stdin.readline().split()))

if cross_product(p1,p2,p3) ==  0 : #일직선
	print(0)
elif cross_product(p1,p2,p3) <  0 : #시계 방향
	print(-1)
else : #반시계 방향
	print(1)

마무리하며

날이 많이 추워졌습니다. 조심하시길. 1일 1백준 오늘 성공!