18052번 - Ghost 스페셜 저지다국어

While sightseeing the Wawel castle in Kraków, your team has been trapped in an ancient chamber by the Ghost. He will not let you out, unless you answer his questions.

On the wall there are n paintings – if we treat the wall as a standard Euclidean plane, the paintings are axis-aligned rectangles. For every painting you know precisely its dimensions and starting location. In some moment – let us call it the moment 0 – Ghost starts moving the paintings, each one in its own direction and speed. As you are an observant team, for every painting you can easily guess its exact speed.

After some time, the Ghost stops the show and starts asking tough questions. Every question consists of two numbers l and r denoting some moments of the show. You must tell Ghost if there was a moment between l and r when some spot on the wall was simultaneously covered by all the paintings. If so, you must also determine the maximal possible common area for all paintings between the moments l and r.

If you want to ever leave this room, better give Ghost the right answers!

The first line of input contains the number of test cases z (1 ≤ z ≤ 4000). The test cases follow, each one in the following format:

The first line of a test case contains the number of paintings n (1 ≤ n ≤ 100 000). Each of the following n lines contains six numbers x₁, y₁, x₂, y₂, v_x, v_y (−1 000 000 ≤ x₁ < x₂ ≤ 1 000 000; −1 000 000 ≤ y₁ < y₂ ≤ 1 000 000; −1 000 000 ≤ v_x, v_y ≤ 1 000 000), where (x₁, y₁) are the coordinates of the lower left corner of the painting, (x₂, y₂) – the upper right corner, and (v_x, v_y) is its speed vector. This means that in the moment t the lower left corner is at the spot (x₁ + tv_x, y₁ + tv_y), and the upper right corner is at (x₂ + tv_x, y₂ + tv_y).

The next line contains the number of Ghost’s questions q (1 ≤ q ≤ 100 000). Each of the following q lines contains two real numbers l, r (0 ≤ l ≤ r ≤ 1 000 000) given with at most 4 decimal places after the separator, meaning that Ghost asks for a closed time interval [l, r].

The total number of paintings in all test cases does not exceed 1 000 000. The total number of questions in all test cases also does not exceed 1 000 000.

For every Ghost’s question output a single real number – the maximal area achieved by the intersection of all the paintings in the given time interval. Your answer will be considered correct if the absolute or relative error is at most 10⁻⁶. In other words, if your program outputs a and the correct value is b, the answer is accepted if |a−b|/max(1,b) ≤ 10⁻⁶.

The intersection may be empty – in that case, your program should output 0 (±10⁻⁶).