문제
2차원 평면에 n(3 <= n <=1,050,000)개의 점이 주어졌을 때 이를 모두 포함하는 최소의 볼록 다각형을 구하는 프로그램을 작성하라.
n개 점의 좌표는 0 이상의 정수로 이뤄져 있으며, 각 222이하의 정수다.
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)으로 만들어 져야 한다.
입력
입력의 첫 줄에는 n 이 입력된다.
그 다음 줄에는 각 점들의 x좌표와 y좌표가 하나씩 입력된다.
x좌표와 y좌표 사이에는 공백이 존재하며, 또한 점과 점 사이에는 공백이 존재한다.
출력
입력에 대해 볼록 다각형을 이루는 좌표들을 (0, 0)부터 시계방향으로 순서대로 출력한다.
예제
10
0 0 2 2 4 8 8 6 1 6 7 0 5 9 3 5 6 0 9 0
0 0 1 6 5 9 8 6 9 0
로그인해야 코드를 작성할 수 있어요.