시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 42 5 4 12.121%

문제

N 개의 반직선이 있다. 각 반직선의 시작점은 y축 선상에 있고, y축과 평행한 반직선은 없다. 각 반직선은 y=Ai*x+Bi의 꼴로 주어진다. 각 반직선은 양수 x에 대해서만 정의된다.

Q개의 질문에 답을 하는 문제를 작성하라. 각 질문은 '직선 y=Cj*x + Dj이 N 개의 반직선과 이루는 교점의 x 좌표 값의 최대값은 무엇인가?'이다.

입력

입력 첫 줄에는 반직선의 개수를 나타내는 자연수 N이 주어진다. 다음 N 줄마다 반직선 방정식의 계수를 나타내는 두 개의 자연수 Ai, Bi가 주어진다. 다음 줄에는 문제의 개수를 타나내는 자연수 Q가 주어진다. 다음 Q 줄에는 두 개의 자연수 E, F가 주어진다. 만약 직전 질문의 직선(y = Cj-1*x + Dj-1)이 N 개의 반직선과 이루는 교점이 적어도 한 개 있었거나 이것이 첫 번째 질문이라면 Cj = E, Dj = F 이다. 그렇지 않으면 Cj = E ^ (229-1) and Dj = F ^ (229-1) 이다. (^는 XOR 연산자.)

제한 사항

  • 입력되는 모든 숫자는 정수이다.
  • -2000000000 < Ai, Bi, Ci, Di < 2000000000
  • 임의의 i, j (i≠j)에 대하여 Ai≠Aj
  • 임의의 i, j에 대하여 Ai≠Cj
  • 임의의 i, j에 대하여 Bi≠Dj
  • 0 < N, Q < 50001

출력

Q개의 질문에 대하여 하나의 실수 x를 소수점 이하 적어도 6자리까지 출력하라. x는 질문에서 주어진 직선이 N 개의 반직선과 이루는 교점의 x 좌표 값의 최대값이다. 만약 직선이 N 개의 반직선과 이루는 교점이 하나도 없다면 "No cross"를 출력하라.

예제 입력

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

예제 출력

0.75000000 
No cross 
1.00000000

힌트

출처

Olympiad > International Tournament in Informatics > Shumen 2012 A3번