Skyball Arena#746
The Magical Sports Federation has decided to create a new flying ball game called Skyball, inspired by traditional broomstick sports. Unlike the usual oval pitch, the innovators proposed using a convex polygon-shaped arena floating in the air. Such an unusual shape would make the game more dynamic and unpredictable.
However, the arena builders faced a challenge. According to the game rules, the arena must be divided by a central line into two zones, and these zones should be as equal in area as possible to ensure fair play. The central line must pass through two vertices of the polygon and divide the arena into two parts so that the ratio of the smaller area to the larger area is as close to as possible, or exactly .
Help the builders find the optimal central line.
The first line contains an integer – the number of test cases (1 \leq T \leq 10). Then test cases follow. Each test case starts with a number – the number of polygon vertices (4 \leq N \leq 2000), followed by lines each with two integers, the coordinates of the polygon's vertices. Coordinates do not exceed in absolute value.
For each test case, print two lines. The first line should contain two numbers – the indices of the vertices through which the dividing diagonal passes, in ascending order. Numbering starts from and corresponds to the order of vertices in the input. The second line should show the irreducible fraction representing the ratio of the areas. If several correct solutions exist, choose the one with the smallest first vertex index. If there is still a tie, choose the one with the smallest second vertex index.
Example 1