This page is still under construction.

Parts of this page are still being built. What you see may change.

Ellipse

Time limit2sMemory limit64 MB

Summary
Given five integer points, either report that no unique ellipse passes through them or compute that ellipse's area to six decimals.
Level

Hard8 of 10

Topics
Geometry, Math, Implementation, Brute force
Solved
No attempts yet

Problem

As a punishment for his conduct during geometry lessons — Alex did nothing while the rest of his class computed the areas of various figures — his geometry teacher gave him a tedious homework assignment.

Alex now has to compute the areas of several ellipses drawn on a sheet of paper torn from a textbook. The sheet has a rectangular grid on it, so the coordinates of points can be read off. Even then, finding the area of an ellipse can be quite involved, especially when the axes of the ellipse are neither vertical nor horizontal.

Being very lazy, Alex wants you to write a program that determines the area of an ellipse from the coordinates of five distinct points lying on it. He will then type in these five points for each ellipse and compute every area this way.

Input

The first line contains the number of ellipses kk (1≤k≤1 0001 \le k \le 1\,000). Each of the next kk lines contains the coordinates of five points lying on the corresponding ellipse, given as x1 y1 x2 y2 … x5 y5x_1\ y_1\ x_2\ y_2\ \dots\ x_5\ y_5. All coordinates are integers whose absolute values do not exceed 1 0001\,000.

Output

For each ellipse, print one line, for a total of kk lines. Print IMPOSSIBLE if the area cannot be determined (there is no ellipse passing through all five given points, or there is more than one such ellipse); otherwise print the area of the ellipse precise to six digits after the decimal point. Whenever such an ellipse exists, it always fits completely inside the textbook page, i.e. every point (x,y)(x, y) of the ellipse satisfies ∣x∣≤1 000|x| \le 1\,000 and ∣y∣≤1 000|y| \le 1\,000.

Examples5

  1. Example 1

    Input
    3
    5 0 0 5 4 3 3 4 -4 -3
    6 1 3 2 -2 -3 -3 -2 1 6
    7 -3 2 7 6 3 5 5 -2 -9
    
    Expected output
    78.539816
    IMPOSSIBLE
    157.079633
    
  2. Example 2

    Input
    1
    10 0 0 10 6 8 8 6 -6 -8
    
    Expected output
    314.159265
    
  3. Example 3

    Input
    1
    10 0 0 5 6 4 8 3 -10 0
    
    Expected output
    157.079633
    
  4. Example 4

    Input
    1
    1 6 2 3 3 2 6 1 -1 -6
    
    Expected output
    IMPOSSIBLE
    
  5. Example 5

    Input
    1
    0 0 1 1 2 4 -1 1 -2 4
    
    Expected output
    IMPOSSIBLE