self.winter.(10). 기하, CCW(외적) _ 백준 [11758, 2166, 17386, 17387]

🧐 외적 관련 알고리즘, CCW ( Counter Clock Wise )

🤔 서로 다른 세점 사이의 넓이를 구하는 공식, CCW란?

CCW(Counter Clock Wise)는 다른 의미로 벡터의 외적값이라고도 한다.
(CCW의 절댓값 / 2)은 세 점의 벡터의 외적값 (세점으로 하는 삼각형 넓이)이다.
이때, 시계방향의 외적값은 음수의 넓이이고
반시계방향의 외적값은 양수의 넓이임을 알 수 있다.

 

CCW = (x1y2 + x2y3 + x3y1) - (x2y1 + x3y2 + x1y3)​

 

보통, 원점을 세 점중 하나에 포함시키게되면 미지수 개수가 줄어들어 계산이 편해진다.

- 이때, 행렬식으로 넓이를 구하는 공식은 다음과 같다. (우리가 익히 들어본 신발끈 공식이다.)

 

 

 

 

 

🧐 백준 11758 (CCW, 외적)    Gold V 

🤫  solution_11758

x1, 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_2166

num = 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_17387

import 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))