- CCW
- 점 3개가 있을 때 이 3점을 이은 방향을 알고자 할 때 쓰는 알고리즘
- https://www.acmicpc.net/blog/view/27
- 두점을 잇는 직선 2개의 벡터들을 외적했을 때
- 값이 -1이면 세점은 시계방향으로 회전
- 값이 0 이면 세점은 한 직선위에
- 값이 1이면 세점은 반시계방향으로 회전한다
def ccw(a, b, c):
return (b[0] - a[0])*(c[1] - a[1])-(c[0] - a[0])*(b[1] - a[1])- convex hull
- 수많은 점들이 있을 때 그중 일부를 이용해 볼록 다각형을 만들되 볼록 다각형 내에 모든 점이 있는 것을 만드는 알고리즘
- 그라함 알고리즘이 대표적인 알고리즘
- 그라함 알고리즘
- O(NlogN)으로 처리가 가능
- 방법 https://red-pulse.tistory.com/182
- https://www.acmicpc.net/problem/1708
1708번: 볼록 껍질
첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범
www.acmicpc.net
import sys
import math
def input():
return sys.stdin.readline().rstrip()
INF = 10e9
N = int(input())
P = [list(map(int, input().split())) for i in range(N)]
S = []
def incl(a, b):
return INF if a[0] == b[0] else (a[1]-b[1])/(a[0]-b[0])
def dist(a, b):
return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
def ccw(a, b, c):
return (b[0] - a[0])*(c[1] - a[1])-(c[0] - a[0])*(b[1] - a[1]) > 0
def convex_hull():
for p3 in P:
while len(S) >= 2:
p1, p2 = S[-2], S[-1]
if ccw(p1, p2, p3):
break
S.pop()
S.append(p3)
return len(S)
P.sort()
P = P[:1] + sorted(P[1:], key = lambda x: incl(x, P[0]))
print(convex_hull())https://www.acmicpc.net/problem/17403
17403번: 가장 높고 넓은 성
첫 번째 줄에 n개의 정수 x1, x2, ..., xn을 공백으로 구분하여 출력한다. xi는 i 번째 표지판이 사용되었을 경우 사용된 층수이며, 사용되지 않았으면 0이다.
www.acmicpc.net
import sys
import math
def input():
return sys.stdin.readline().rstrip()
INF = 10e9
N = int(input())
P = [list(map(int, input().split())) for i in range(N)]
ans = [0] * N
def incl(a, b):
return INF if a[0] == b[0] else (a[1]-b[1])/(a[0]-b[0])
def dist(a, b):
return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
def ccw(a, b, c):
return (b[0] - a[0])*(c[1] - a[1])-(c[0] - a[0])*(b[1] - a[1])
def convex_hull(prev_P, cur):
S = []
sorted_P = sorted(prev_P)
sorted_P = sorted_P[:1] + sorted(sorted_P[1:], key = lambda x: (incl(x, sorted_P[0]), dist(x, sorted_P[0])))
for p3 in sorted_P:
while len(S) >= 2:
p1, p2 = S[-2], S[-1]
if ccw(p1, p2, p3) > 0:
break
S.pop()
S.append(p3)
if len(S) <= 2:
return sorted_P, S
ans[P.index(S[0])] = cur
sorted_P.remove(S[0])
for i in range(2, len(S)):
if ccw(S[i-2], S[i-1], S[i]) != 0:
ans[P.index(S[i-1])] = cur
sorted_P.remove(S[i-1])
ans[P.index(S[-1])] = cur
sorted_P.remove(S[-1])
return sorted_P, S
prev_P = P.copy()
cur = 1
while True:
prev_P, k = convex_hull(prev_P, cur)
if len(k) <= 2:
break
cur += 1
print(*ans)