[Python] 기하

# 12-1. 기하 알아보기

기하 핵심 이론

• CCW(Counter-ClockWise)는 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘이다.
• 세 점을 A(X1, Y1), B(X2, Y2), C(X3, Y3)라 할 때, CCW = (X1Y2 + Y2X3 + X3Y1) - (X2Y1 + X3Y2 + X1Y2)
• CCW의 결과가 <0인 경우 시계 방향, ==0인 경우 일직선, >0인 경우 반시계 방향으로 세 점이 위치한다.

 

https://www.acmicpc.net/problem/11758

import sys
input = sys.stdin.readline

x1 ,y1 = map(int, input().split())
x2 ,y2 = map(int, input().split())
x3 ,y3 = map(int, input().split())

# CCW 공식
result = (x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3)

if result >0:
    print(1)
elif result<0:
    print(-1)
else:
    print(0)

• CCW공식을 그대로 적용

 

 

https://www.acmicpc.net/problem/17387

import sys
input = sys.stdin.readline

x1,y1,x2,y2 = map(int, input().split())
x3,y3,x4,y4 = map(int, input().split())

# CCW 함수
def CCW(x1,x2,y1,y2,x3,y3):
    temp = (x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3)
    if temp > 0:
        return 1
    elif temp == 0:
        return 0
    return -1

# 선분 겹침 여부 판별 함수
def isOverlab(x1,x2,y1,y2,x3,y3,x4,y4):
    if min(x1,x2)<=max(x3,x4) and min(x3,x4)<=max(x1,x2) and min(y1,y2)<=max(y3,y4) and min(y3,y4) <= max(y1,y2):
        return True
    return False

def isCross(x1,y1,x2,y2,x3,y3,x4,y4):
    abc = CCW(x1,x2,y1,y2,x3,y3)
    abd = CCW(x1,x2,y1,y2,x4,y4)
    cda = CCW(x3,x4,y3,y4,x1,y1)
    cdb = CCW(x3,x4,y3,y4,x2,y2)
    if abc*abd==0 and cda*cdb==0: # 선분이 일직선일 때
        return isOverlab(x1,x2,y1,y2,x3,y3,x4,y4) # 겹치는 선분인지 판별
    elif abc*abd <= 0  and cda*cdb<=0: # 선분이 교차하는 경우
        return True
    return False

cross = isCross(x1,y1,x2,y2,x3,y3,x4,y4)

if cross:
    print(1)
else:
    print(0)

• A-B 선분을 기준으로 점C와 점 D를 CCW한 값의 곱과 C-D 선분을 기준이로 점 A와 B를 CCW한 값의 곱이 모두 음수이면 두 선분은 교차한다.
• 선분이 교차하는 경우는 CCW의 방향이 다를 때만 발생하기 때문.
• 만약 두 선분이 겹치는 경우 CCW의 결괏값은 0이다. 겹치지 않는 경우는 한 선분의 min값이 다른 선분의 max값보다 클 때이다.

 

 

https://www.acmicpc.net/problem/2162

• 하다가 뭔가..틀렸는데 못팢았어 새로운 코드를 찾았다. 로직은 똑같음.

import sys
from collections import Counter

input = sys.stdin.readline


def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y


class Line:
    def __init__(self, p1: Point, p2: Point):
        self.p1 = p1
        self.p2 = p2


def direction(a: Point, b: Point, c: Point):
    dxab = b.x - a.x
    dxac = c.x - a.x
    dyab = b.y - a.y
    dyac = c.y - a.y

    # AB 기울기 > AC 기울기
    if dxab * dyac < dyab * dxac:
        dir = 1
    # AB 기울기 < AC 기울기
    elif dxab * dyac > dyab * dxac:
        dir = -1
    # AB 기울기 == AC 기울기
    else:
        if dxab == 0 and dyab == 0:
            dir == 0
        if dxab * dxac < 0 or dyab * dyac < 0:
            dir = -1
        elif dxab * dxab + dyab * dyab >= dxac * dxac + dyac * dyac:
            dir = 0
        else:
            dir = 1
    return dir


def intersection(l1: Line, l2: Line):
    if direction(l1.p1, l1.p2, l2.p1) * direction(l1.p1, l1.p2, l2.p2) <= 0 and \
            direction(l2.p1, l2.p2, l1.p1) * direction(l2.p1, l2.p2, l1.p2) <= 0:
        return True
    return False


# N개의 선분
N = int(input())

lines = []
parent = [i for i in range(N)]

for i in range(N):
    x1, y1, x2, y2 = map(int, input().rstrip().split())
    line = Line(Point(x1, y1), Point(x2, y2))
    lines.append(line)

for i in range(N):
    for j in range(i+1, N):
        if intersection(lines[i], lines[j]):
            union_parent(parent, i, j)

parent = [find_parent(parent, x) for x in parent]

cnt = Counter(parent)
print(len(cnt))     # 그룹의 수
print(max(cnt.values()))        # 가장 크기가 큰 그룹에 속하는 선분의 개수

• 변형된 유니온-파인드 알고리즘을 이용한다. 부모 노드 리스트는 모두 -1로 초기화한다.
• 값이 양수라면 parent[i]로 이동하고, 음수라면 현재 노드가 대표 노드이다. 해당 음수의 절댓값이 현재 선분 그룹에 연결되어 있는 선분의 개수가 된다.
• union함수를 이용해 두 대표 노드가 같으면 리턴하고, 다르면 두 대표 노드를 연결해 하나의 선분 그룹으로 만든다. 대표 노드를 연결할 때 먼저 대표가 될 노드(p)에 새롭게 합쳐지는 선분 그룹의 개수를 음수(q)로 더한다.
• 선분을 입력받으며 이전 선분과 교차되는지 확인한다.
• 최종적으로 부모 리스트에서 음수 데이터의 개수(그룹의 수, ans)와 최솟값의 절댓값(가장 큰 그룹의 선분 수)를 절댓값으로 출력한다.

 

 

https://www.acmicpc.net/problem/2166

import sys
input = sys.stdin.readline

N = int(input())
x = []
y = []

for i in range(N):
    tempX, tempY = map(int, input().split())
    x.append(tempX)
    y.append(tempY)

# 마지막에 처음 점 다시 넣기
x.append(x[0])
y.append(y[0])

result = 0

for i in range(N):
    result += (x[i]*y[i+1]) - (x[i+1]*y[i]) # CCW값을 결괏값에 더하기

print(round(abs(result/2),1)) # 둘째 자리 반올림

• CCW는 벡터의 외적값을 의미하기도 한다. 따라서 CCW(A,B,C)의 절댓값 == 평행사변형의 넓이 이다.
• CCW의 절댓값을 2로 나누면 세 점을 꼭짓점으로 하는 삼각형의 넓이를 구할 수 있다.
• 점들이순서대로 제공되지만 반시계/시계 방향은 알 수 없으므로 원점과 순서대로 오는 두 점 간의 CCW값들의 합을 절댓값으로 변경하고 2로 나눈다.
• 원점과 다른 두 점 사이의 CCW 공식은 단순화가 가능하다. CCW = x1y2 - x2y1

 

 

---

# 회고

 

기하 오랜만...

이 파트는 실제 코딩테스트에서는 그닥 본 적은 없다.

공식을 알고 있는게 중요할 듯함