곧은 막대기를 세 개씩 가지고 있는 학생들이 모든 막대기를 바닥으로 던졌다. 각자 가지고 있던 막대기를 최대 한 개를 제거할 때, 바닥에 있는 나머지 막대기들이 서로 겹치지 않을 수 있는 지를 알아보기로 하였다. 단, 막대기가 제거될 때 다른 막대기의 위치는 변하지 않는다고 가정한다. 예를 들어, 학생 세 명이 각자 가지고 있는 막대기 ①②③, ④⑤⑥, ⑦⑧⑨를 바닥에 던진 막대기 모양이 아래와 같을 때, 막대기 한 개씩 ②, ④, ⑧을 제거하면 나머지 여섯 개의 막대기는 서로 겹치지 않게 된다
또한, 학생 두 명이 던진 막대기 모양이 아래와 같은 경우에는 각자 어떠한 막대기를 한 개씩 제거하더라도 나머지 막대기들 중에서 적어도 두 개는 서로 겹치게 된다.
바닥에 던져진 막대기의 양 끝점의 좌표가 주어졌을 때, 바닥에 남아 있는 막대기들이 서로 겹치지 않도록 각자 가지고 있던 막대기들 중에서 제거할 최대 한 개의 막대기를 찾는 프로그램을 작성하시오. |
첫째 줄에는 학생들의 수를 나타내는 정수 N이 주어진다. N은 2 이상 1,000 이하이다. 두 번째 줄부터 3N개의 줄에는 한 줄에 막대기 한 개의 양 끝에 해당되는 두 끝점의 좌표를 나타내는 네 개의 정수 X1, Y1, X2, Y2가 빈칸을 사이에 두고 나타난다. 각 정수는 한 개의 막대기의 두 끝점의 좌표 (X1, Y1), (X2, Y2)를 나타낸다. 이 정수들은 –10,000 이상 10,000 이하이다. 두 번째 줄부터 나타나는 각 막대기는 1번부터 3N번까지 순서대로 번호가 부여되며, 연속적인 세 개의 번호 3i-2, 3i-1, 3i (1<=i<=N)는 i번째 학생이 가지고 있는 막대기 세 개의 번호를 나타낸다.
입력 데이터는 다음 세 조건을 항상 만족한다고 가정한다.
(조건 1) 막대기들의 끝점의 좌표가 같은 경우는 없다.
(조건 2) 세 개의 끝점이 임의의 일직선상에 위치하는 경우는 없다.
(조건 3) 세 개의 막대기가 한 점에서 만나는 경우는 없다.
첫째 줄에는 서로 겹치지 않도록 막대기를 제거할 수 없는 경우에는 -1을 출력한다. 그렇지 않은 경우에는 첫째 줄에 제거된 막대기의 수인 K (0<=K<=N)를 출력한다. K가 최소일 필요는 없다. 두 번째 줄에는 제거된 막대기 K개의 번호를 빈칸을 사이에 두고 오름차순으로 출력한다. 단, K가 0인 경우에는 막대기 번호를 출력하지 않는다. 답이 여러 개인 경우에는 그 중 하나를 출력한다.