시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB67141125.581%

문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 전편에서 N개의 직선을 가지고 성공적인 놀이를 만들어낸 원숭이는 이제 또 다른 문제를 만들어내고야 말았다!!

문제는 정말 간단하다. 좌표평면상에 N개의 직선이 주어진다. 그리고 Q개의 질문이 주어진다. 각 질문은 (x, a)로 이루어져 있는데 a가 1이면 그 x값에서 N개의 직선 중의 최대값을 구하고, a가 2면 그 x값에서 N개의 직선 중의 최소값을 구하면 된다.

N개의 직선 중에는 축과 평행한 직선은 없다. N개의 직선과 Q개의 질문이 주어졌을 때, 각 질문에 답을 하는 프로그램을 작성하시오.

입력

첫째 줄에 직선의 개수 N과 질문의 개수 Q가 주어진다. N은 1이상 100,000이하의 정수이고, Q는 0이상 100,000이하의 정수이다. 그 다음부터 N줄에 걸쳐 각 직선의 정보가 주어진다. 각 직선을 y = ax+b로 나타냈을 때의 a, b가 주어진다. a, b는 -10,000이상 10,000이하의 정수이다. 그 다음부터 Q줄에 걸쳐 질문이 주어진다. 각 질문은 x a의 형식으로 들어온다. x는 -1,000,000.0이상 1,000,000.0이하인 실수이고 소숫점 첫째자리 안으로 주어진다. a는 1 또는 2이다.

출력

Q줄에 걸쳐 각 질문에 알맞은 실수를 출력한다. 절대 오차는 10-4까지 허용한다.

예제 입력 1

3 2
0 2
1 1
2 -2
-3 2
2 1

예제 출력 1

-8.000
3.000

출처

  • 문제를 만든 사람: ntopia