농장

농장은 2차원 유클리드 평면으로 볼 수 있다. 나무는 $n$그루이며 $1, 2, \dots, n$번으로 번호가 매겨져 있다. 각 나무는 평면 위의 한 점이고, $i$번 나무의 좌표는 $(x_i, y_i)$이다. 나무들의 좌표는 모두 서로 다르다.

P 씨는 원점 $(0,0)$에서 차를 몰기 시작한다. 한 라운드마다 왼쪽, 오른쪽, 위, 왼쪽 위 45도, 오른쪽 위 45도 중 한 방향을 고른다. 그 방향으로 가면 아직 방문하지 않은 나무에 도달할 수 있어야 고를 수 있다. 선택한 방향으로 곧장 달려 그 방향에서 가장 가까운 미방문 나무에 도착한다. 고를 수 있는 방향이 없으면 멈춘다. P 씨는 가장 많은 나무를 방문하는 최적 경로를 따른다. 최적 경로가 여러 개라면 그중 아무거나 골라도 된다.

S 씨는 P 씨의 차가 농장에 바퀴 자국(rut)을 남긴다는 것을 알아챘다. 바퀴 자국은 두 나무 사이, 또는 원점과 나무 사이의 선분이다. S 씨는 왼쪽과 오른쪽이 아닌 방향(위, 왼쪽 위 45도, 오른쪽 위 45도)의 바퀴 자국이 보기 좋지 않다고 본다. 그래서 그런 자국이 생길 수 있는 구간을 다지려고 롤러를 빌리기로 했다. 정확히는, 최적 경로 중 하나에 포함되는 선분들이 그 구간이다.

롤러는 다음 규칙으로 움직인다.

• 원점 또는 임의의 나무에서 출발한다.
• 위, 왼쪽 위 45도, 오른쪽 위 45도 방향으로 움직일 수 있다. 멈추거나 방향을 바꾸는 것은 나무 위에서만 가능하다.
• 왼쪽이나 오른쪽이 아닌 바퀴 자국이 생길 수 있는 구간만 지날 수 있다. 한 구간을 여러 롤러가 지나도 된다.

P 씨와 S 씨는 두 가지를 묻는다. (1) P 씨의 최적 경로를 구하라. (2) 필요한 롤러의 최소 개수를 구하라.

첫 줄에 나무의 개수 $n$이 주어진다. 다음 $n$개의 줄에는 $i$번째 나무의 좌표 $x_i$와 $y_i$가 공백 한 칸으로 구분되어 주어진다.

출력은 세 줄이다. 첫째 줄에는 P 씨가 방문할 수 있는 나무의 최대 개수 $m$을 출력한다. 둘째 줄에는 P 씨가 방문하는 나무 번호 $m$개를 공백으로 구분해 출력한다. 셋째 줄에는 필요한 롤러의 최소 개수를 출력한다.