Hits

안녕하세요. 모카의 머신러닝 입니다. 이번 포스팅에서는 백준 알고리즘 문제 풀이에 대해 포스팅하도록 하겠습니다.


코드는 이곳을 참고했음을 밝힙니다.


1. 기하

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

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)


백준 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):
    temp = (x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3)
    if temp > 0:
        return 1
    elif temp < 0:
        return -1
    return 0

def isOverlab(x1, y1, x2, 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, y1, x2, y2, x3, y3)
    abd = CCW(x1, y1, x2, y2, x4, y4)
    cda = CCW(x3, y3, x4, y4, x1, y1)
    cdb = CCW(x3, y3, x4, y4, x2, y2)
    if abc*abd == 0 and cda*cdb == 0:
        return isOverlab(x1, y1, x2, 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)


백준 2162번

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

import sys
input = sys.stdin.readline
N = int(input())
parent = [-1] * (3001)

def CCW(x1, y1, x2, 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 -1
    return 0

def isOverlab(x1, y1, x2, 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, y1, x2, y2, x3, y3)
    abd = CCW(x1, y1, x2, y2, x4, y4)
    cda = CCW(x3, y3, x4, y4, x1, y1)
    cdb = CCW(x3, y3, x4, y4, x2, y2)
    if abc * abd == 0 and cda * cdb == 0: 
        return isOverlab(x1, y1, x2, y2, x3, y3, x4, y4) 
    elif abc * abd <= 0 and cda * cdb <= 0: 
        return True
    return False

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

L = []
L.append([])
for i in range(1, N + 1):
    L.append([])
    L[i] = list(map(int, input().split()))
    for j in range(1, 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);

ans = 0
res = 0

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

print(ans)
print(-res)


백준 2166번

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])
    
print(round(abs(result/2), 1))


지금까지 백준 알고리즘 기하 부분이었습니다.

읽어주셔서 감사합니다. 😃