Convex Hull 구현하는 방법이 정말 많던데, 저는 다음과 같이 구현합니다.
1. 점의 정보는 구조체로 저장할 수도 있지만, std::pair<int, int>로 저장하는 것이 더 간편할 수도 있습니다. std::pair로 구현할 경우 좋은 점이 "2번"에서 나타납니다.
2. 입력 받은 점들 중 x좌표와 y좌표가 가장 작은 점을 찾아, 그 배열의 가장 첫 번째 원소(index가 0인)와 바꿉니다.
2-1. 이 때, std::pair를 사용했다면, 한 줄만에 간단히 이 짓을 해결할 수 있습니다. (!!) swap(arr[0], *min_element(arr, arr+N)); <- koosaga님께서 이렇게 하시길래 배웠어요
3. 위의 소스에서는 함수를 2개(*_product 꼴의 long long형 함수) 구현하셨지만, clock-clockwise 함수(자칭 ccw)만 짜도 충분히 구현 가능합니다.
3-1. ccw 함수는 3개의 점을 인자로 받습니다. ccw(A, B, C)꼴로 구현했다고 할 때, O(1)만에 A->B->C의 선분들이 "일직선"인지, "시계방향으로 꺾였"는지, "반시계방향으로 꺾였"는지 알 수 있습니다.
4. convex hull를 구하기 전에 점을 정렬할 필요가 있습니다. 저는 정렬을, 첫 번째 원소에 대한 각도가 작은 순으로 정렬합니다.
4-1. 이 때, 정렬을 위해 bool cmp함수를 구현할 필요가 있습니다. 예는, 그냥 배열의 첫 번째 원소와 ccw를 한 번만 해서 구현할 수 있습니다.
4-2. 임의의 두 점이 배열의 첫 번째 원소와 일직선 상에 있을 경우, 가까운 점이 먼저 오도록 합니다.
4-3. 정렬을 할 때, 첫 번째 원소는 빼고 정렬을 하도록 합니다. sort(arr+1, arr+N);
5. vector를 사용하든, 직접 구현하시든 해서, 정렬된 점들을 한 번 쓱 읽으시면서 열심히 push와 pop을 해주시면 됩니다.
쓰다보니 글이 더럽네요. 조금이나마 도움이 되셨음 합니다.
구현한 함수 : long long ccw, bool cmp
medic_programmer 7년 전 1
간단한 convex hull 이라 그냥 덤볐는데 ㅠㅠ
고수님들 조언 부탁드립니다.