시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 27 2 2 10.000%

문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그는 수학을 매우 좋아하는 원숭이였다. 그래서 그는 N개의 직선을 가지고 기발한 문제를 생각해냈다.

문제는 이렇다. 좌표평면상에 N개의 직선과 상수 K가 주어진다. 직선은 모두 fi(x) = ai * x + bi의 꼴로 나타낼 수 있다. 그랬을 때 함수 g(x)를 {f1(x), f2(x), ..., fN(x)}의 중간값으로 정의하면, g(x) = K가 되는 x를 모두 찾는 문제이다.

입력

첫째 줄에 직선의 개수 N과 상수 K가 주어진다. N은 3이상 1,000,000이하인 홀수이고, K는 -10,000이상 10,000이하인 정수이다. 그 다음 줄부터 각 줄마다 두 개의 정수 ai, bi (0 <= ai <= 1,000,000 , -1,000,000 <= bi <= 1,000,000) 가 주어진다. 중복되는 직선은 없다.

출력

첫째 줄에 g(x) = K 인 x의 구간의 시작과 끝을 출력한다. 각 수는 소수점 넷째자리에서 반올림하여 출력한다. 만약 x가 무한대로 발산하는 경우, 양의 무한대는 +inf, 음의 무한대는 -inf 로 출력하면 된다. g(x) = K를 만족하는 x가 존재하지 않는다면 "impossible"을 출력하면 된다. 답이 되는 구간이 1개 이하인 경우만 입력으로 들어온다.

예제 입력

5 3
2 -12
3 -4
0 3
2 -3
1 -1

예제 출력

3.000 4.000

힌트

-0.000 을 출력하지 않도록 주의한다. -0.0005 초과, 0.0005 미만의 수는 0.000 으로 출력하게 하면 된다.

출처

  • 문제를 만든 사람: ntopia