쓰러지는 카드

시간 제한1초메모리 제한128 MB

요약

서로 교차하지 않는 카드들이 세워져 있을 때, 카드 하나가 넘어지면 높이 H의 직사각형 영역을 쓸며 닿는 카드를 쓰러뜨리고, 맞은 카드는 미는 카드 반대쪽으로 넘어진다. 이때 최종적으로 넘어지는 카드 번호를 오름차순으로 구한다.

난이도: 보통10점 중 6점
유형: 기하, 시뮬레이션, BFS
정답자: 아직 제출이 없습니다

문제

카드를 모서리로 세우는 것은 어렵지만, 어떤 사람이 끈기 있게 $N$ 장의 카드를 책상 위에 짧은 모서리로 세워 두었다. 위에서 내려다보면 각 카드는 책상 위의 선분으로 나타나며, $i$ 번 카드는 점 $(x_i, y_i)$ 에서 $(v_i, w_i)$ 까지 이어진다. 모든 카드의 높이는 $H$ 로 같고, 어떤 두 선분도 서로 교차하지 않는다.

첫 번째 카드가 넘어져 바닥에 눕는다. 카드가 눕을 때 카드의 직사각형 면이 책상 위의 영역을 덮는다. 밑변인 선분은 그대로 있고, 카드는 그 선분을 넘어지는 방향(선분에 수직인 방향)으로 거리 $H$ 만큼 확장한 직사각형을 덮는다. 이 직사각형이 아직 서 있는 카드의 선분에 닿으면 그 카드도 넘어진다.

첫 번째 카드가 넘어지는 방향은 벡터 $(x_1, y_1) \to (v_1, w_1)$ 을 반시계 방향으로 $90^\circ$ 회전시킨 방향이다.

넘어지는 카드 $A$ 가 서 있는 카드 $B$ 에 닿으면, $B$ 는 자기 선분에 수직인 두 방향 중, 넘어지는 방향을 따라 나아가는 반직선이 카드 $A$ 의 선분을 담은 직선을 가로지르지 않는 방향으로 넘어진다. 즉 밀어낸 카드에서 멀어지는 쪽으로 넘어진다.

입력은 다음 경우를 절대 포함하지 않는다.

자신을 밀어낸 카드에 대해 정확히 수직으로 넘어지는 카드
하나보다 많은, 서 있는 카드에 닿는 넘어지는 카드

어떤 카드가 넘어지고 어떤 카드가 서 있는지 판정하여라.

입력

첫째 줄에 카드의 수 $N$ 과 카드의 높이 $H$ 가 주어진다 ( $1 \le N \le 100$ , $H > 0$ , $H$ 는 실수). 다음 $N$ 개의 줄에는 각각 네 실수 $x_i\ y_i\ v_i\ w_i$ 가 공백으로 구분되어 주어지며, 이는 $i$ 번 카드 선분의 양 끝점 좌표이다.

출력

넘어지는 카드들의 번호를 증가하는 순서로 공백으로 구분하여 출력한다.

예제5

예제 1

입력

3 100
10 10 50 40
10 0 50 30
20 90 20 20

예상 출력

1 3

예제 2
입력
```
1 10
0 0 10 0
```
예상 출력
```
1
```
예제 3
입력
```
2 10
0 0 10 0
2 5 8 5
```
예상 출력
```
1 2
```
예제 4
입력
```
3 10
0 0 10 0
2 5 8 5
3 12 7 12
```
예상 출력
```
1 2 3
```

예제 5

입력

예상 출력

1 2 3 4 5 6