쓰러지는 카드

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

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

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

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

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

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

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

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

입력

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

출력

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