CCW3 백준(BOJ) 16190 Rising Sun ** # ccw #include #include #include using namespace std; int n; pair pos[2001]; pair home; int ans = -1; long long ccw(pair a, pairb, pair c) { return a.first * b.second - b.first*a.second + b.first *c.second - c.first *b.second + c.first * a.second - a.first * c.second; } int main() { scanf("%d", &n); for (int i = 0; i < 2 * n; i++) scanf("%lld", &pos[i].first); scanf("%lld", &home.first); for (in.. 2018. 10. 7. [알고리즘 정리] 그라함 알고리즘(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. [알고리즘 정리] CCW(Counter Clock Wise) 알고리즘 CCW는 3점을 이은 선분의 방향성에 대해서 찾는 방법이다. 찾는 방법은 삼각형의 넓이 구하는 공식을 이용한다.공식은 생각보다 어렵지 않다. 2S의 절대값에 나누기 2를 한 값이 세점의 삼각형의 넓이가 된다. 여기서 세 점의 방향성을 알기위해 2S값을 주목한다.P1이 파랑, p2 주황, P3 초록 일 때, 시계방향이면 2S의 값이 +, 일직선이면 0, 반시계방향이면 - 값을 가지게 됩니다. 관련 문제 : 백준(BOJ) 2987 사과나무 ** 2018. 5. 31. 이전 1 다음
