|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|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.
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