cfranck   5년 전

코딩 테스트에서 본 문제입니다. 너무 풀고 싶습니다만 어떤 키워드로 검색을 해야 힌트라도 얻을 수 있는건지 통 모르겠어서 여기에 질문 올려봅니다. 

(고정된) 길이의 끈과 2차원 평면상 점들의 (x, y) 좌표가 주어졌을때, 그 끈으로 완전히 묶을 수 있는 점(즉 그 끈으로 만든 다각형의 내부에 포함되는 점)들의 갯수가 최대한이 되게 하려면?

convex hull이 관련이 있는 것 같은데, 그걸로 검색을 하면 주어진 점을 전부 다 포함하는 제일 바깥쪽 볼록 다각형을 구하는 방법만 나와서요. 이런 종류의 문제는 어떻게 접근해야 하나요? 구체적인 답을 주시지는 않아도 됩니다. (아니, 주지 마세요^^) 참고가 될만한 자료를 알려주시면 제가 찾아보고 궁리해보겠습니다.

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