[일반] 2차원 평면 위의 n개의 점 중 k개를 골라 가장 큰 다각형 만들기 질문

[익명(1.247)]

이런 문제를 푸는 알고리즘이 있을까요????

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(1.247)]

컨벡헐은 근데 완성됐을때 점이 k개인게 보장이 안되니...

[p플랫(urd05)]

3개, 4개의 경우에 제곱으로 푸는 문제는 존재하고 (요새 건설 등) k개는 대충
https://koosaga.com/245
이 글의 마지막 practice problem과 유사한 거 같은데 잘은 모르겠다.

[익명(1.247)]

제곱으로 푸는건 뭔가요?? ㄷㄷ

[시아닌(kimjg1119)]

convex hull 위에서 dp돌리면 되는듯
https://math.stackexchange.com/questions/1953393/finding-maximum-area-k-gon-given-a-set-of-points

[익명(121.125)]

convex hull원소가 k개 미만이면 망하지않나

[익명(121.188)]

그럼 그냥 컨벡스 헐이 정답이지

[익명(1.247)]

ㄷㄷ감사함다