6개의 댓글이 있습니다.
-
-
JongMan -
제가 이 문제를 아는 건 아니라 맞는지 모르긴 하는데, 한번 찍어보죠. :)
Graham's Scan 을 한다고 합시다. 마지막으로 선택한 두 점 a, b 를 알고 있죠. 이 때 우리는 다음 점 c 를 보고 난 뒤, ccw(a, b, c) 의 부호에 따라 b 를 버리거나, c 를 스택에 추가하거나 합니다. 이렇게 하는 대신, 선택지를 만들기로 합시다.
1) a->b->c 가 오른쪽으로 꺾이는 경우: c 를 무시하고 (이 문제에선 무시할 수 있으니깐) 다음 정점 d 로 넘어간다
2) a->b->c 가 왼쪽으로 꺾이는 경우: c를 추가하고, (b,c) 를 마지막 두 정점으로 해서 convex hull 을 만들어 본다.
그리고 나서 c 다음의 d, e, f 에 대해 (a,b,d), (a,b,e), (a,b,f)... 를 각각 테스트해 보고 위를 반복합니다. 이렇게 하면 모든 subset 에 대한 convex hull 이 만들어지지 않나.. 싶은데요.
(a->b->c 이 오른쪽으로 꺾일 때 b를 빼고 c를 넣는 연산이 필요 없는 이유는, ? 와 a 가 마지막 두 점일 때 b 후에 c를 곧장 시도하는 경우가 있기 때문에 이미 이 경우를 세고 있기 때문입니다)
그래서, [x,y] 가 마지막 두 정점일 때 convex hull 의 최대 각도 수를 c[x,y] 라고 하면
c[x,y] = sum(z = y+1 to n, x->y->z turns left)c[y,z] + 1
머 대충 이런 식으로 되지 않을까 찍어봅니다. 코딩은 안해봤으니 틀릴 수도 있고, 그러면 아래 다른 고수분들이 고쳐주시겠죠.. ~_~
15년 전 link
-
-
-
Dynamical -
이 방법은 graham scan에서 쓰이는 스택과는 관련이 없기 때문에 앞서 convex hull과 관련이 적다고 말씀드렸지만 이 방법을 convex hull을 구하는 또다른 방법인 jarvis march와 유사한 측면에서 생각을 하면 관련이 있다고도 볼수 있네요.
일단 맨 처음에는 특정 다각형의 맨 밑점이 될 점을 하나 택합니다. ................. N
그리고 그 밑점에 대해서 graham scan 할 때처럼 정렬을 하고,
그보다 윗점들에 대해서 다이나믹을 작성합니다. (그 아래점은 아예 필요가 없으므로 고려할 때 배제하면 되죠.)
........................ N^3을 유지하려면 이 부분이 N^2이 되어야 겠죠?
1. 마지막 두 점이 (i , j)인 부분에서 마지막 두 점이 (j , k)인 부분으로 넘어갈 때
2. 마지막 두 점이 (i , j)인 부분에서 마지막 두 점이 (i , k)인 부분으로 넘어갈 때
여기서 k는 다수의 선택이 아닌 단 1가지의 선택입니다.
1번에서 (i , j)에서 (j , k)로 넘어갈 때에는, 다수의 k가 필요 없는 이유는 2번 때문입니다. 1번에서는 (i , j)에서 (j , k)로 넘어갈 때 가장 적게 꺾이는 점 k를 택합니다. 2번에서는 (i , j)에서 (i , k)로 넘어갈 때 선분 (i , j)를 기준으로 반시계 방향으로 회전시 가장 적게 회전하는 점을 k로 합니다. 이렇게 하면 1번에서 다수의 k를 고려할 필요가 없는데,
그것은 더 많이 꺾이는 점 p에 대해서 어차피 (i , j) -> (j , p)의 과정을 (i , j) -> (j , k) -> (j , k2) -> .... -> (j , km) -> (j , p)의 과정을 통하여 처리가 되기 때문입니다.
즉 이차원 다이나믹을 이용해서 N^3을 맞춰줄 수 있습니다.
15년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Stun
계속 남의 글 보면서 좋은 정보 얻어가다가 궁금한 것이 생겨서 질문을 드려봅니다 :)
문제의 알고리즘은 Convex Hul입니다.
1. 우선 문제의 직접적인 링크는 여기 입니다.
문제를 설명 드리면 x, y좌표의 시퀀스가 입력으로 들어오면 그 중 일부의 점을 선택하여 Convex Hull을 만들었을 때 만들수 있는 최대의 n 각형을 찾는 것입니다.
N의 상한은 250 이기 때문에 모든 경우를 처리 하는건 당연히 불가능 할테고.. 무슨 방법이 있겠지 하고 생각 하는데 잘 안풀리네요 :)
부탁드리겠습니다.
15년 전