🧐 외적 관련 알고리즘, CCW ( Counter Clock Wise )
🤔 서로 다른 세점 사이의 넓이를 구하는 공식, CCW란?
CCW(Counter Clock Wise)는 다른 의미로 벡터의 외적값이라고도 한다.
(CCW의 절댓값 / 2)은 세 점의 벡터의 외적값 (세점으로 하는 삼각형 넓이)이다.
이때, 시계방향의 외적값은 음수의 넓이이고
반시계방향의 외적값은 양수의 넓이임을 알 수 있다.
CCW = (x1y2 + x2y3 + x3y1) - (x2y1 + x3y2 + x1y3)보통, 원점을 세 점중 하나에 포함시키게되면 미지수 개수가 줄어들어 계산이 편해진다.
- 이때, 행렬식으로 넓이를 구하는 공식은 다음과 같다. (우리가 익히 들어본 신발끈 공식이다.)
🧐 백준 11758 (CCW, 외적) Gold V
🤫 solution_11758x1, y1 = map(int, input().split()) x2, y2 = map(int, input().split()) x3, y3 = map(int, input().split()) CCW = (x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3) if CCW < 0: print(-1) if CCW > 0: print(1) if CCW == 0: print(0)
🧐 백준 2166 (CCW, 외적) Gold V
🤫 solution_2166num = int(input()) x , y = [] , [] for i in range(num): X, Y = map(int,input().split()) x.append(X) y.append(Y) x.append(x[0]) y.append(y[0]) S = 0 for i in range(num): S += (x[i]*y[i+1] - x[i+1]*y[i]) print(round(abs(S)/2, 1))
🧐 백준 17386, 17387 (CCW, 외적) Gold III, Gold II
🤫 Algorithm
https://velog.io/@jini_eun/%EB%B0%B1%EC%A4%80-17387%EB%B2%88-%EC%84%A0%EB%B6%84-%EA%B5%90%EC%B0%A8-2-Java-Python
🤫 solution_17387import sys input = sys.stdin.readline x1, y1, x2, y2 = map(int, input().split()) x3, y3, x4, y4 = map(int, input().split()) point = [] point.append([x1, y1]) point.append([x2, y2]) point.append([x3, y3]) point.append([x4, y4]) A, B, C, D = point[0], point[1], point[2], point[3] def ccw(p1, p2, p3): X1, X2, X3 = p1[0], p2[0], p3[0] Y1, Y2, Y3 = p1[1], p2[1], p3[1] CCW = (X1*Y2 + X2*Y3 + X3*Y1) - (X2*Y1 + X3*Y2 + X1*Y3) if CCW > 0: return 1 elif CCW < 0: return -1 else: return 0 def checkCross(a, b, c, d): result = 0 p123, p124 = ccw(a, b, c), ccw(a, b, d) p341, p342 = ccw(c, d, a), ccw(c, d, b) if (p123 * p124 <= 0 and p341 * p342 <= 0) or (p123 * p124 == 0 and p341 * p342 == 0): if min(a[0], b[0]) <= max(c[0], d[0]) and \ min(c[0], d[0]) <= max(a[0], b[0]) and \ min(a[1], b[1]) <= max(c[1], d[1]) and \ min(c[1], d[1]) <= max(a[1], b[1]): result = 1 return result print(checkCross(A, B, C, D))
