[백준] CCW (11758번) - Python

🐳 문제 - [백준] CCW (11758번)

---

 

 

🐳 알고리즘 - CCW ( Counter Clock Wise ) 

---

🎯 CCW 란 ?

CCW 알고리즘은 좌표평면 위의 세 점이 이루는 관계를 알기 위한 알고리즘이다.

 

먼저 식부터 살펴보면 아래의 식과 같습니다.

우선 위의 식이 어디서 나왔는지 알아야합니다.

 

위의 식은 좌표 평면 위의 세 점이 만드는 삼각형의 넓이를 벡터의 외적을 이용해 구하는 식입니다.

먼저 세 점을 이용해 두 벡터를 만듭니다. 저는 (x1,y1) 을 기준으로 두 벡터를 만들어 주겠습니다.

그 럼 두 벡터를 v1, v2 라고 합시다. v1 = (x2-x1, y2-y1), v2 = (x3-x1,y3-y1) 이 됩니다.

이 두 벡터를 외적해 줍니다. 외적한 결과는 크기와 방향을 가집니다. 

 

외적한 값의 크기는 두 벡터가 만드는 평행사변형의 넓이 = S 입니다.

방향을 정하는 방법은 다음과 같습니다.

 

1. v1의 끝점과 v2 벡터의 시작점을 이어 줍니다.

2. 손 바닥을 펴 v1 방향으로 엄지를 제외한 손가락을 향해줍니다.

3. v2 방향으로 손가락을 감아줍니다.

4. 그 때 엄지가 가르키는 방향이 외적벡터의 방향입니다.

 

이렇듯 CCW 는 삼각형의 넓이를 외적을 이용해 구할 때 나오는 식이고 이 식은 방향성과 크기를 가지는 외적 값입니다.

이 때 외적의 방향성을 이용해서 두 벡터가 이루는 관계가 반시계인지 시계인지 알 수 있게 되는 것입니다.

 

CCW의 결과에 따라 

CCW > 0 인 경우 세 점이 이루는 방향이 반시계 방향

CCW = 0 인 경우 세 점이 일직선

CCW < 0 인 경우 세 점이 이루는 방향이 시계 방향이라고 합니다.

 

이 관계를 그림으로 보면 다음과 같습니다. 

 

 

후에 선 분의 교차 검증, 컨벡스헐 등의 다양한 기하 알고리즘에 이 CCW 알고리즘이 사용됩니다.

 

 

🐳 코드

---

import sys

f = sys.stdin

points = [list(map(int,f.readline().rstrip().split())) for _ in range(3)]

x1,y1 = points[0]
x2,y2 = points[1]
x3,y3 = points[2]

if (x3-x1)*(y2-y1) - (y3-y1)*(x2-x1) > 0:
    print(-1)
elif (x3-x1)*(y2-y1) - (y3-y1)*(x2-x1) == 0:
    print(0)
else:
    print(1)