2차원 평면에 n(3 <= n <=1,050,000)개의 점이 주어졌을 때 이를 모두 포함하는 최소의 볼록 다각형을 구하는 프로그램을 작성하라.

n개 점의 좌표는 0 이상의 정수로 이뤄져 있으며, 각 2²²이하의 정수다.

n개 점 중에 맨 왼쪽에 위치한 좌표는 (0,0)이며, 맨 오른쪽에 위치한 좌표는 (r,0)이다. 이를 제외한 점들의 x 좌표는 1 이상 r-1이하이다.

한 x좌표에 두 개의 점이 동시에 위치하는 경우는 없다고 가정한다. 또한 볼록 다각형을 이루는 점은 최대가 되어야 한다.

만약 점이 (0,0), (1,1), (2,2), (3,0)일 경우 볼록 다각형은 (0,0), (1,1), (2,2), (3,0)으로 만들어 져야 한다.

Convex Hull timer 1s memory - MB

Convex Hull 1s - MB