블록껍질1 [알고리즘 정리] 그라함 알고리즘(Graham’s scan) 알고리즘 ccw 알고리즘(?)을 이용하여 블록 껍질(convex hull)을 뽑아내는 알고리즘 입니다. CCW(Counter Clock Wise) 알고리즘 시간복잡도는 O(nlogn) # 풀이 순서 1. 가장 x, y가 작은 ori점을 찾는다. 2. ori 이외의 점들을 반시계 방향을 정렬한다. 3. ccw를 활용하여 블록 껍질을 찾는다. ccw>0이 되었을 때만 스택에 넣어주면 된다. # 관련문제 : https://www.acmicpc.net/problem/1708 #include #include #include #include #include #include #include #include #include #define MAX 200005 #define INF 987654321 #define MOD 31991.. 2018. 8. 26. 이전 1 다음
