nuclear852   9달 전

convexhull까지는 Graham Scan으로 잘 짰는데

점이 원 위에 나올 때, 점이 최대 20만개가 될 수 있잖아요??

그래서 최대 거리를 찾을 때 시간을 줄여보려고

이분 탐색을 생각했거든요,

예를 들어 한 점에서 다른 점까지의 최대 거리를 찾을 때

다른 점-1, 다른점 +1 의 거리보다 큰 것이 만족하면, 그 다른 점이 최대 거리잖아요? convex polygon이니까

근데 이렇게 해서 찾아도 시간 초과가 걸려서 말입니다.. ㅠㅠㅠ

혹시 다른 방법 없을까요..? 아니면 코딩이 잘 못된건가요...?

booboo   9달 전

호옥시 이게 바이너리서치의 기본 가정을 만족하나요?
예를 들어 컨벡스 폴리곤의 정점 $V = {v_1,v_2, ..., v_n}$ 에 대해서 $v_i$ 기준으로 찾으려는 점(가장 먼 점)이 $v_j$라고 할 때 $v_{i+1}, v_{i+2}, ..., v_{j-1}$와 $v_{j+1}, v_{j+2}, ..., v_n, v_1, ..., v_{i-1}$ 이 말씀하신 조건을 만족하지 않을 수 있는데, 만약 left = i + 1, right = n + i - 1 (답이 어디 있을지 모르니까 탐색 대상이 원형일 경우엔 선형 두 개를 붙인 배열을 생각하는게 좋습니다)로 해서 답을 구하려 할 경우 바이너리 서치가 제대로 동작하지 않겠죠.

대신 말씀하신 설명을 보면 대신 함수가 볼록한 모양을 가질텐데(V 이런 모양이나 U 이런 모양에 가까운), 여기서의 극값을 구할 때 Ternary Search 를 사용하면 쉽게 구할 수 있습니다. 점들이 원형인 것에 주의해서 다시 구해보세요.

*사실 컨벡스 헐을 만들고 나면 $O(n^2)$으로도 통과가 됩니다(!)
*안 된다면 윗껍질 아래껍질로 반 쪼개서 구해보세요(답은 당연히 윗껍질 한 개, 아랫껍질 한 개를 골랐을 때 겠죠).
*C++을 이용하시는데 std::sort를 쓰시는 건 어떤지..

booboo   9달 전

http://ilyoan.tistory.com/entry/Ternary-Search
http://wcipeg.com/wiki/Ternary_search

그리고 생각해보니 바이너리 서치의 가정을 깨지 않고 사용하려면 $distance(v_i, v_{j-1}) < distance(v_i, v_j)$ 인 최대 $j$를 찾으면 되겠네요 :)

nuclear852   9달 전

오옹 감사합니다.

v_i 기준으로 가장 먼 점을 v_j라 할떄

v_j만 항상 distance( v_i, v_j-1) 과 distance( v_i, v_j+1) 보다 크다고 생각하고 각각의 v_i에 대해서 모든 최대 distance를 구한다음에 비교하는 방향으로 짜려고 했는데... 흠... 원형을 고려했어야 했는데 이 부분을 까먹고 있었네요...

사실 제가 코딩 초보자라 sort를 이용해서 struct array를 sort할 때 comparison function을 어떻게 짜야 할지 막막해서 그냥 quicksort를 직접 만들었어요 ㅠㅠ

혹시 comparison function을 어떻게 짜야하는지 도움 좀 얻을 수 있을까요..? ㅠㅠ

그리고 또 궁금한게 있는데 만약 모든 점이 원 위에 있는 경우 그 점들은 다 convex polygon인데 어떻게 20만개의 점이 O(n^2)으로 해결되는지 궁금합니다!


isac322   9달 전

std:: sort에 comparison function을 쓰려면 함수의 매개변수와 반환 타입만 맞추면 상관이 없는데, 예를들어

vector<T> arr;이 있다면

bool comparison(const T &L, const T &R);와같은 함수의 틀만 맞추면

sort(arr.begin(), arr.end(), comparison);처럼 사용이 가능합니다.

그리고 comparison 함수의 반환값은 매개변수에서 L이 R보다 앞에있다면 false를, 반대라면 true를 반환하게 만드시면됩니다.


O(n2)인 방법은 n개의 점들로 가능한 모든 두 쌍을 확인하면 됩니다.

nuclear852   9달 전

std::sort는 잘 해결했습니다.

그런데 O(n^2)으로 짜봤는데 1%에서 막히더군요...

혹시 graham scan이 잘 못 된 건가요??

nuclear852   9달 전

해결됐네여

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