moner_ari   8달 전

[문제]

2차원 좌표평면 상에 x축에 평행한 서로 다른 두 직선 y = hupper, y = hlower가 있으며, 이들 직선을 연결하는 n개의 선분이 있다. 각 선분의 한쪽 끝점의 y좌표는 hupper이며, 다른 끝점의 y좌표는 hlower이다. 모든 선분의 끝점은 서로 다르며, 1부터 n까지의 자연수로 번호가 순서대로 매겨져 있다.

두 직선 y = hupper와 y = hlower 사이에 있는 x축에 평행한 직선 y = hi를 생각하자. (이들 직선은 m개의 쿼리로 주어진다.) 당연하겠지만, 직선 y = hi는 모든 선분과 교차한다. 이때 직선 y = hi와 교차하는 선분 중에서 가장 왼쪽에 위치한 선분이 어떤 것인지 구하려 한다. 물론 입력으로 주어지는 n개 선분 중에서 서로 다른 2개 이상의 선분이 한 점에서 교차할 수도 있으며, 2개 이상의 선분이 만나는 교점을 직선 y = hi가 지나는 형식으로 입력이 주어질 수도 있다. 이 경우에는, 직선 y = hi와 교차하는 선분 중에서 직선 y = hupper와의 교점의 x좌표가 가장 작은 선분이 가장 왼쪽에 있다고 정의한다.

예를 들어, 아래 <그림>과 같이 두 직선을 연결하는 5개의 선분과 3개의 쿼리로 주어지는 직선이 있다고 하자. 직선 y = 2.0, y = 4.0과 접하는 선분 중 가장 왼쪽에 있는 선분의 번호가 각각 2, 3임은 쉽게 알 수 있다. 직선 y = 6.25와 접하는 선분 중 가장 왼쪽에 있는 선분의 번호는 3, 4가 되는데, 앞서 언급한 정의에 의해 y = hupper와의 교점의 x좌표가 더 작은 4번 선분이 가장 왼쪽에 있는 선분이 된다.

<그림> - 생략.

2개의 직선을 연결하는 n개의 선분과 m개의 쿼리가 주어질 때, 각 쿼리마다 가장 왼쪽에 있는 선분을 구하는 프로그램을 작성하시오.

주의: 하나의 점에서 2개 이상의 선분이 교차할 수 있다. 특히 입력으로 실수가 주어지는 만큼, 실수 연산 과정에서 부동 소수점 오차로 인해 실수를 할 수도 있으니 각별히 주의할 것.

--------

[입력]

입력은 표준 입력을 사용한다.

입력의 첫 줄에는 두 정수 maxY, minY가 주어진다. (-1,000 ≤ minY < maxY ≤ 1,000) maxY, minY는 각각 좌표평면에서 x축에 평행한 직선 y = hupper, y = hlower에서 hupper, hlower의 값에 해당한다.

입력의 2번째 줄에는 두 직선 사이를 연결하는 선분의 개수를 나타내는 정수 n이 주어진다. (1 ≤ n ≤ 100,000)

다음 n개 줄에는 각 선분과 위쪽 직선, 아래쪽 직선과의 교점의 x좌표를 나타내는 두 정수 upperX, lowX가 주어진다. (-500,000 ≤ upperX, lowX ≤ 500,000) n개 줄의 입력은 1번 선분부터 n번 선분까지 순서대로 주어지며, n개 선분의 upperX, lowX의 값은 서로 다르다.

다음 줄에는 쿼리의 개수를 나타내는 정수 m이 주어진다. (1 ≤ m ≤ 100,000)

다음 m개 줄에는 x축에 평행한 직선 y = hi 쿼리가 순서대로 주어진다. 이때 hi은 minY ≤ hi ≤ maxY를 만족하는 실수로, 소수점 아래 자릿수는 1자리 이상 3자리 이하로 주어진다.

--------

[출력]

출력은 표준 출력을 사용한다.

m개 줄에 각 쿼리에서 가장 왼쪽의 선분의 번호를 나타내는 1개의 정수를 한 줄에 하나씩 출력한다.

댓글을 작성하려면 로그인해야 합니다.