#214986. [ICPC 2020 Yokohama R] Solar Car

Alice and Bob are playing a game of baggage delivery using a toy solar car. A number of poles are placed here and there in the game field.

At the start of a game, the solar car is placed right next to a pole, and the same or another pole is marked as the destination. Bob chooses one of the poles and places the baggage there. Then, Alice plans a route of the car to pick up the baggage and deliver it to the marked destination. Alice chooses the shortest possible route and Bob should choose a pole to maximize the route length.

The solar car can drive arbitrary routes but, as it has no battery cells, it would stop as soon as it gets into shadows. In this game, a point light source is located on the surface of the field, and thus the poles cast infinitely long shadows in the directions opposite to the light source location. The drive route should avoid any of these shadows.

When the initial positions of the solar car and the destination are given, assuming that both players make the best choices, the length of the drive route is uniquely determined.

Let us think of all the possible game configurations with given two sets of poles, one for the start positions of the solar car and the other for the destinations. When both the initial car position and the destination are to be chosen uniformly at random from the corresponding sets, what is the expected route length?

Your task is to compute the expected value of the route length, given the set of the initial positions of the car and that of the destinations.

The input consists of a single test case of the following format.

Here, is the number of poles (). The poles are numbered 1 through and the -th pole is placed at integer coordinates (, ). The point light is at . Poles are not placed at nor in a shadow of another pole, and no two poles are placed at the same coordinates.

is the number of pairs of sets (). The -th pair of sets is specified by four integers (, ). Specifically, the solar car is initially placed at the -th pole, with chosen uniformly at random from , and the destination pole is also chosen uniformly at random from .

Output the answer for each pair of sets. Absolute or relative errors less than are permissible.

样例输入 1

5
7 0
3 3
0 7
-3 3
-7 0
6
1 1 3 3
3 3 4 4
1 1 5 5
5 5 2 2
2 2 4 4
1 5 1 5

样例输出 1

24.000000000000
20.440306508911
20.000000000000
19.000000000000
15.440306508911
21.606571644990

For the first set pair of this test case, the solar car is placed at and the flag is placed at . Then, Bob places the baggage at . The length of the shortest route from to is 10, because the straight path from to crosses the shadow of pole 4. The length of the shortest route from to is 14, so the total length is 24.

:::align{center}

Figure F.1. Shortest routes for the first five set pairs of Sample Input 1. Black dots are the positions of the poles and gray lines are their shadows. The yellowish brown dots are the positions of the point lights. For each figure, the red lines indicate the shortest route from the initial car position to the destination. :::