안녕하세요. 모카의 머신러닝 입니다. 이번 포스팅에서는 백준 알고리즘 문제 풀이에 대해 포스팅하도록 하겠습니다.
코드는 이곳을 참고했음을 밝힙니다.
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))
지금까지 백준 알고리즘 기하 부분이었습니다.
읽어주셔서 감사합니다. 😃