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

문제

You are given N rays (half-lines) with initial points on the Oy axis. None of the rays is parallel to the Oy axis. The rays are given in the form y = Ai*x + Bi. Each ray is only defined for positive x.

Write a program lines that answers Q queries of the type: What is the maximal xcoordinate of an intersection point of the line y = Cj*x + Dj with one of the given N rays.

입력

On the first line of the standard input is given a single positive integer N, the number of the rays. On each of the next N lines are given the two integers: Ai and Bi, the coefficients of the equation of each ray. On the next line a single positive integer Q is given, the number of queries. On each of the following Q lines are given two integers E and F. If the previous line had crossed one of the rays, or if this is the first line, these are the coefficients of the equation of the current line (Cj = E, Dj = F). Otherwise, the coefficients of the equation of the line are Cj = E ^ (229-1) and Dj = F ^ (229-1), where ^ is the XOR operation.

Constraints

  • All the numbers in the input are integers.
  • -2000000000 < Ai, Bi, Ci, Di < 2000000000
  • All numbers Ai are different.
  • Each Cj is different from any of the numbers Ai.
  • Each Dj is different from any of the numbers Bi
  • 0 < N, Q < 50001 

출력

For each question output a single real number x with at least 6 digits after the decimal point, the maximal x-coordinate of a point in which the current line crosses one of the given rays. If the line doesn't cross any ray, output "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번

  • 잘못된 조건을 찾은 사람: koosaga