EDOC 2024-1 7회차 과제 (기하 알아보기)

12-1. 기하 알아보기

 

097. CCW (백준 11758번)

 

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 = (x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3)

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

 

ccw의 결과값을 통해 세 점의 위치 관계를 파악할 수 있다.

ccw = (x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3)

 

(정답)

 

---

 

098. 선분 교차 2 (백준 17387번)

 

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

def ccw(x1, y1, x2, y2, x3, y3):
    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

isCross = False

l1p3 = ccw(x1, y1, x2, y2, x3, y3)
l1p4 = ccw(x1, y1, x2, y2, x4, y4)
l2p1 = ccw(x3, y3, x4, y4, x1, y1)
l2p2 = ccw(x3, y3, x4, y4, x2, y2)

if l1p3 * l1p4 == 0 and l2p1 * l2p2 == 0:
    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):
        isCross = True
elif l1p3 * l1p4 <= 0 and l2p1 * l2p2 <= 0:
    isCross = True

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

한 선분과 다른 선분의 각 점의 ccw를 구하는 것이 이 문제의 핵심이다. 두 선분이 교차하려면 한 선분에 대해 다른 선분의 한 점과의 ccw 부호와 다른 한 점과의 ccw 부호가 달라야 하기 때문이다.

여기까지 생각하면 되는 문제가 선분 교차 1이다. https://jungh150c.tistory.com/116

이 문제(선분 교차 2)에서는 세 점, 혹은 네 점이 일직선에 놓일 수도 있기 때문에 이 경우도 생각해야 한다.

elif l1p3 * l1p4 <= 0 and l2p1 * l2p2 <= 0: 여기서 선분 교차 1 문제와 달리 등호가 필요한 이유는 다음과 같은 경우를 고려하기 위해서이다.

(정답)

 

---

 

099. 선분 그룹 (백준 2162번)

 

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

 

import sys
input = sys.stdin.readline

n = int(input())
parent = [-1] * n
l = []

def ccw(x1, y1, x2, y2, x3, y3):
    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 isCross(x1, y1, x2, y2, x3, y3, x4, y4):
    cross = False

    l1p3 = ccw(x1, y1, x2, y2, x3, y3)
    l1p4 = ccw(x1, y1, x2, y2, x4, y4)
    l2p1 = ccw(x3, y3, x4, y4, x1, y1)
    l2p2 = ccw(x3, y3, x4, y4, x2, y2)

    if l1p3 * l1p4 == 0 and l2p1 * l2p2 == 0:
        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):
            cross = True
    elif l1p3 * l1p4 <= 0 and l2p1 * l2p2 <= 0:
        cross = True

    return cross

def find(a):
    if parent[a] < 0:
        return a
    parent[a] = find(parent[a])
    return parent[a]

def union(a, b):
    p = find(a)
    q = find(b)
    if p == q:
        return
    parent[p] += parent[q]
    parent[q] = p

for i in range(n):
    l.append(list(map(int, input().split())))
    for j in range(i):
        if isCross(l[i][0], l[i][1], l[i][2], l[i][3], l[j][0], l[j][1], l[j][2], l[j][3]):
            union(i, j)

cnt = 0
ans = 0

for i in range(n):
    if parent[i] < 0:
        cnt += 1
        ans = min(ans, parent[i])

print(cnt)
print(ans * (-1))

앞에서 푼 선분 교차2 문제와 유니온 파인드를 결합시켜야 하는 문제였다. 그냥 어느 집합에 속해있는지 또는 집합의 개수만 구하는 게 아니라 집합에 속한 선분의 개수도 구해야하기 때문에 parent 배열에 저장하는 값을 집합에 포함된 선분 개수로 계속 업데이트 해주는 것이 아이디어였던 것 같다. 암튼 어려웠다... (정답)

 

---

 

100. 다각형의 면적 (백준 2166번)

 

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

 

import sys
input = sys.stdin.readline

n = int(input())
x = [0] * (n + 1)
y = [0] * (n + 1)

for i in range(n):
    x[i], y[i] = map(int, input().split())

x[n] = x[0]
y[n] = y[0]

ans = 0
for i in range(n):
    ans += (x[i] * y[i + 1] - x[i + 1] * y[i])

print(round(abs(ans / 2), 1))

코드는 정말 간단한데... 원리를 이해하는 게 정말 어려웠다. (정답)