스파이 네트워크 계획

조니는 본부에서 커다란 지도를 발견했다. 지도에는 여러 점이 초록색 또는 빨간색 두 가지 색으로 표시되어 있었다. 그는 당시 이것을 별로 신경 쓰지 않았다. 나중에야 그 지도에 서로 다른 색으로 그려진, 스파이 네트워크를 재편하는 두 가지 계획이 담겨 있었다는 사실을 알게 되었다.

재편의 핵심 아이디어는 요원들을 여러 지점에 나누어 배치하는 것이다. 각 지점은 본부가 직접 관리한다. 한 지점에 요원이 여러 명 있을 수 있다. 이때 그 지점은 배치될 요원 수만큼 지도에 반복해서 표시된다.

점들의 집합이 관할하는 영역은 원래 점 집합을 모두 포함하는 볼록 집합 가운데 넓이가 가장 작은 것이다. 모든 점이 한 직선 위에 있다면, 모든 점을 포함하는 선분 가운데 길이가 가장 짧은 것이 그 영역이다.

조니는 점들이 어디에 있었는지는 기억하지만, 어느 점이 첫 번째 계획에 속하고 어느 점이 두 번째 계획에 속했는지는 기억하지 못한다. 그는 또 다른 계획의 점들이 관할하는 영역이 서로 겹쳐서 두 계획 모두 실행할 수 없었다는 것도 기억한다. 마지막으로 기억하는 것은, 한쪽 색의 점이 다른 쪽보다 훨씬 많았다는 사실이다.

조니는 점들이 두 계획에 어떻게 나뉠 수 있었는지 알고 싶어 한다. 형식적으로 말하면, 서로 다른 색 점들이 관할하는 영역이 교차하면서 두 집합의 점 개수 차이가 최대가 되도록 점들을 나누는 방법을 찾아라.

첫 줄에 점의 개수를 나타내는 정수 $n$이 주어진다 ($4 \le n \le 10^5$).

이어서 $n$개의 줄에 지도 위 점의 좌표를 나타내는 두 정수 $x_i$와 $y_i$가 한 줄에 하나씩 주어진다 ($-10^9 \le x_i, y_i \le 10^9$).

원하는 분할이 존재함이 보장된다.

첫 줄에 두 집합 중 크기가 작은 집합의 크기 $m$을 출력한다.

둘째 줄에는 그 집합에 속한 점들의 번호 $m$개를 출력한다.

최적해가 여러 개라면 어떤 답을 출력해도 된다.