이차함수와 직선

시간 제한0.1초메모리 제한1024 MB

요약

최고차항 계수가 1 또는 -1인 이차함수 N개 중에서 모든 직선이 적어도 하나와 만나도록 하는 최소 개수의 함수를 골라 번호를 출력합니다.

난이도: 어려움10점 중 8점
유형: 기하, 수학, 그리디
정답자: 아직 제출이 없습니다

문제

Azber와 Biou는 2차원 좌표평면에서 게임을 한다.

게임을 시작하기 전에 Azber는 자신이 그릴 수 있는 $N$ 개의 이차함수를 가지고 있다. Azber가 가지고 있는 이차함수의 이차항 계수는 $1$ 또는 $-1$ 이다.

처음에 Azber는 가지고 있는 이차함수 중 몇 개를 좌표평면 위에 그린다.

Biou가 모든 이차함수와 만나지 않는 직선을 그릴 수 있으면 Biou가 이기고, Biou가 어떤 직선을 그리더라도 이차함수 하나 이상과 만나면 Azber가 이긴다.

Azber가 이길 수 있다면, 좌표평면에 그리는 이차함수의 개수를 최소로 해서 이기고 싶다.

Azber가 이길 수 있는지 판정하라. 이길 수 있다면 좌표평면에 그려야 하는 이차함수의 최소 개수와, 그 경우에 그리는 이차함수를 구하라.

입력

첫 번째 줄에 그릴 수 있는 이차함수의 개수 $N$ 이 주어진다. $(1 \le N \le 20\,000)$

다음 $N$ 개의 줄에 정수 $X_i$ , $Y_i$ , $Z_i$ 가 주어진다. $(1 \le i \le N;$ $|X_i|=1;$ $-5\,000 \le Y_i \le 5\,000;$ $-2.5 \times 10^7 \le Z_i \le 2.5 \times 10^7)$

이는 Azber가 가지고 있는 $i$ 번째 이차함수가 $y = X_i x^2 + Y_i x + Z_i$ 라는 뜻이다.

출력

Azber가 Biou를 이길 수 없다면 -1을 출력한다.

이길 수 있다면, 첫 줄에 Azber가 사용하는 이차함수의 최소 개수를 출력한다. 다음 줄에는 Azber가 사용하는 이차함수의 번호를 공백으로 구분해서 출력한다.

최소 개수의 이차함수로 이기는 경우가 여러 개라면 그중 아무거나 출력한다.

예제3

예제 1
입력
```
2
1 0 1
-1 0 -1
```
예상 출력
```
-1
```
예제 2
입력
```
2
1 0 -1
-1 0 1
```
예상 출력
```
2
1 2
```

예제 3

입력

예상 출력

3
2 3 4