펍 크롤

앨이 더블린에 막 도착했다. 그는 가진 돈을 더블린에서 유명한 활동인 펍 크롤에 쓰려고 한다. 목표는 같은 펍을 두 번 가지 않으면서 서로 다른 펍을 최대한 많이 돌고, 각 펍에서 기네스를 한 파인트씩 마시는 것이다. 더블린에는 펍이 $n$ 개 있다.

앨은 술에 빨리 취해서 펍을 평면 위의 점으로 보고, 한 펍에서 다음 펍으로 가는 길을 두 점을 잇는 직선으로 본다. 실제 길은 골목을 여러 번 지나거나 건물을 돌아가거나 다음 펍을 찾느라 제자리를 맴도는 길일 수도 있지만, 앨은 그런 사정에 신경 쓰지 않는다. 앨이 신경 쓰는 것은 자기가 하는 모든 회전이 좌회전이어야 한다는 것뿐이다. 즉 경로에서 연속한 세 펍에 대해, 세 번째 펍은 첫 번째 펍에서 두 번째 펍으로 향하는 방향 직선의 왼쪽 반평면에 있어야 한다. 더블린의 건설업자도 펍 크롤을 즐긴 덕분에, 한 직선 위에 펍을 세 개 이상 지은 적은 없다.

앨이 방문할 수 있는 펍의 최대 개수를 구하고 경로를 짜자.

첫째 줄에 펍의 개수 $n$ 이 주어진다. ($1 \le n \le 5000$)

다음 $n$ 개 줄에 펍 하나의 좌표를 나타내는 두 정수 $x$ 와 $y$ 가 주어진다. ($-10^9 \le x, y \le 10^9$)

서로 다른 펍은 서로 다른 점에 있다.

첫째 줄에 앨이 방문할 수 있는 펍의 최대 개수 $m$ 을 출력한다. 둘째 줄에 앨이 방문하는 순서대로 펍 번호 $m$ 개를 공백 하나로 구분해 출력한다. 펍 번호는 입력에 나온 순서대로 1번부터 $n$ 번까지다.

조건을 만족하는 경로는 여러 개일 수 있으므로, 다음 규칙으로 정해지는 경로 하나만 정답으로 인정한다.

• 출발 펍은 $y$ 좌표가 가장 작은 펍이다. 그런 펍이 둘 이상이면 그중 $x$ 좌표가 가장 작은 펍에서 출발한다.
• 현재 펍에서 다음 펍을 고를 때는, 아직 방문하지 않은 펍 $q$ 중에서 방문하지 않은 나머지 펍이 모두 현재 펍에서 $q$ 로 향하는 방향 직선의 왼쪽에 오는 $q$ 를 고른다. 한 직선 위에 펍이 세 개 이상 없으므로 이런 $q$ 는 매 단계마다 정확히 하나 있다. 방문하지 않은 펍이 하나만 남으면 그 펍을 고른다.