Line Fighter 2
시간 제한1초메모리 제한1024 MB
N개의 직선과 (x, a) 형태의 질의 Q개가 주어질 때, x에서 모든 직선의 값 중 a=1이면 최댓값, a=2이면 최솟값을 1e-4 오차로 구한다.
문제
동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 전편에서 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까지 허용한다.