간단한 convex hull 이라 그냥 덤볐는데 ㅠㅠ

고수님들 조언 부탁드립니다.

yclock   9달 전

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

yclock   9달 전

점을 좌표 순으로 정렬한 다음, 위쪽 convex hull과 아래쪽 convex hull를 따로 구하는 방법도 있던데,

저는 설명하기 어렵네요. 사실 자기도 이해가 되지 않는다는 점은 비밀

말씀하신 코딩 기술은 STL을 익힌 후에 꼭 적용해보도록 하겠습니다!! (아직 초보라..)

그러면 일직선인 경우에 대한 처리는 어떻게 하셨나요?

(저는 CCW 함수를 두 개 구현한 것이 아니라 CCW와 동일한 기능을 하는 녀석(cross_product, 외적이죠) 과 일직선 처를 위해 내적 함수를 하나 더 구현했습니다)

그리고 혹시 예외가 나는 경우도 하나 들어주실 수 있나요??

yclock   9달 전

STL을 배우시지 않았다고 가정하고, 점을 구조체로 정의해 보겠습니다.

struct Point{ int x, y; };

long long ccw(const Point& A, const Point& B, const Point& C) 함수는, A->B->C가 일직선일 경우 0을, 오른쪽으로 꺾일 경우 음수를, 왼쪽으로 꺾일 경우 양수를 반환합니다.

ccw(A, B, C) { return (A.x*B.y + B.x*C.y + C.x*A.y) - (A.y*B.x + B.y*C.x + C.y*A.x); }

자세히 보면 규칙이 있음을 알 수 있습니다.

yclock   9달 전

문제의 예제를 예로 들겠습니다.

입력에서 주어진 점들을 모두 P에 저장하고, swap(P[0], *min_element(P, P+N))나 다른 것들을 통해 P[0]에 가장 좌표가 작은 점을 저장하도록 합니다.

0-indexed에 주의해 주세요!


즉, P[0] 에는 (1, 1)이 들어가 있을 겁니다.

이 때, P[0]을 기준으로 기울기(각도) 순으로 정렬을 시행합니다.

정렬 후에는 P가 다음과 같이 저장되어 있을 겁니다. P = {(1, 1), (2, 1), (3, 1), (3, 2), (2, 2), (2, 3), (1, 2), (1, 3)}

여기서 주의할 점은, 일직선에 있는 점은 P[0]와 가까운 점이 먼저오도록 처리해야 합니다.

yclock   9달 전

예외의 의미를 모르겠습니다;; (난독증이 있어서)

제 소스가 왜 오답처리되는지도 알려주셨으면 해서요 ㅎㅎ

일직선인 경우 거리순정렬을 하는 이유가 무엇인가요?

yclock   9달 전

이제 봤어요 죄송해요ㅠㅠ

먼 거부터 정렬이 되어 있다면, convex hull을 생성할 때, 일직선 위에 있는 점들이 싸그리 무시됩니다.

음,... 그냥 해보고 결과를 보면 편할 듯 싶네요;;

일단 님이 주신 힌트로부터 코드의 많은 부분을 개선했습니다. 특히 거리순 정렬이 효과가 좋더군요. 여러가지로 많이 배웠습니다 :)


다만 왜 타 채점사이트에선 모두 ACCEPT되는데 여기서만 FAIL이 뜰까요..

yclock   9달 전

으악! 효과가 좋다고 하시다니! 정말 감사합니다! ^^

만일 원하신다면, 소스를 보내드릴 의향이 있습니다. 타 사이트에서 ACCEPT 받으셨으니 괜찮겠지..?

이메일이나 기타 경로 등을 알려주세요.


아! 소스 이제 봤네요(인터넷 딜레이). 검토해보도록 하겠습니다! ^^

yclock   9달 전

cross_produce(A, B, C, D)가 어떤 함수인가요..?

CCW의 원리가 벡터의 외적이라 A-B 의 위치벡터, C-D의 위치벡터의 외적의 부호를 통해 시계.반시계를 판단했습니다

CCW와 같은 함수라 보시면 됩니다.


메일은 [email protected] 입니다.

yclock   9달 전

cmp함수에서 A나 B중 하나가 St와 일치하는 경우에 예외 처리를 하는 것이 좋을 듯 합니다.

(저는 그것 때문에 몇 분 정도 날렸죠 ㅠ)

일치해도 어차피 ccw=0 이고 거리도 0이기 때문에 제일 앞으로 갈 듯 한데요?

yclock   9달 전

long long ccw = cross_product(St,A,St,B);

이거 하나 고치니 정답이 나오네요

으악ㅠ

yclock   9달 전

오버플로우에 조심합시다! ^^

와미친.... 소름이네요

long long으로 일부러 바꿨는데 ㄷㄷ 그걸 놓치다니 ㅠㅠㅠㅠㅠ

감사합니다!!!! 중학생이신가요??

yclock   9달 전

올해 중3됩니다.

제가 많이 어린데, 어리광(으응?) 많이 받아주셔서 정말 감사합니다!

ㅎㅎ 대단하십니다.

그런 어리광이라면 얼마든지 받아들일 수 있습니다 ㅋㅋㅋㅋ

농담이고 1년 열심히 하셔서 좋은 고등학교 가길 바랄게요 :)

댓글을 작성하려면 로그인해야 합니다.