막대기
시간 제한1초메모리 제한128 MB
학생마다 세 개의 막대가 있을 때, 각자 최대 한 개씩 제거해 남은 막대들이 서로 교차하지 않게 만들 수 있는지 판단하고 제거할 막대 번호를 출력합니다.
문제
각 학생은 곧은 막대기 세 개를 가지고 있다. 학생들이 모든 막대기를 바닥에 던진 뒤, 각 학생이 자신이 가진 막대기 중 최대 한 개를 제거할 수 있다고 하자. 제거하지 않고 남긴 막대기들이 서로 교차하지 않도록 만들 수 있는지 판단해야 한다. 막대기를 제거해도 다른 막대기의 위치는 변하지 않는다.
가령 학생 세 명이 가진 막대기 ①②③, ④⑤⑥, ⑦⑧⑨가 아래 그림처럼 놓여 있다면, ②, ④, ⑧을 제거하여 남은 여섯 개의 막대기가 서로 교차하지 않게 만들 수 있다.
반면, 학생 두 명이 던진 막대기가 아래 그림처럼 놓인 경우에는 각 학생이 어떤 막대기를 하나씩 제거하더라도 남은 막대기 중 적어도 두 개가 서로 교차한다.
바닥에 놓인 각 막대기의 양 끝점 좌표가 주어진다. 각 학생의 막대기 중 최대 한 개씩을 제거하여 남은 막대기들이 서로 교차하지 않도록 할 수 있는지 판단하고, 가능하다면 제거할 막대기 번호를 출력하라.
입력
첫째 줄에 학생 수를 나타내는 정수 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을 출력한다.
가능하다면 첫째 줄에 제거한 막대기의 수 K를 출력한다. K는 0 이상 N 이하이며, 최소일 필요는 없다. 둘째 줄에는 제거한 K개 막대기의 번호를 공백으로 구분해 오름차순으로 출력한다. K가 0이면 둘째 줄은 출력하지 않는다.
가능한 답이 여러 개라면 그중 아무 답이나 출력해도 된다.