RSS Feed

볼록 구멍

Problem 252

출제 일시 : 2020-11-12 00:02:35

평면 위의 점의 집합이 있을 때, 주어진 점 중 몇 개를 꼭지점으로 하고 다른 어떤 점도 그 안에 포함하지 않는 볼록 다각형을 볼록 구멍이라 정의합니다.(다른 점들이 다각형의 둘레에 있을 수는 있습니다)

예를 들어, 아래 그림은 20개의 점으로 된 집합과 몇몇 그런 볼록 구멍입니다. 빨간 7변형 볼록 구멍의 면적은 1049694.5 이고, 주어진 집합으로 만들 수 있는 볼록 구멍의 최대 면적입니다.

위의 보기는 아래 유사 난수 생성기의 첫 20개 점을 사용했습니다: (T2k−1, T2k), 여기서 k = 1,2,…,20 입니다:

S0 =  290797 
Sn+1 =  Sn2 mod 50515093
Tn =  ( Sn mod 2000 ) − 1000 

즉, (527, 144), (−488, 732), (−454, −947), … 입니다.

유사 난수 생성기의 첫 500개 점으로 된 집합으로 만들 수 있는 볼록 구멍의 최대 면적은 얼마입니까?
답은 소수점이하 첫자리까지 제출하세요.


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.