Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Minimum Time Travel

By sabertooth · Limits 3s, 512 MB

A famous time traveler, Adam is planning for his final move against the time cycle. He has the coordinates of every person in Winden. He needs to find the group of persons among the given coordinates such that area of polygon created by these positions is positive and minimum among all other possibilities then he will make time travel with them.

In other words, he wants to select a non-empty subset among the given set such that the area of polygon created by these coordinate is minimum and positive.

But Adam skipped high school and forgot how to do this simple task. He needs your help. He will give you a set of points. You need to select a subset from these coordinates and find the area of the polygon that is minimum and positive.

It is guaranteed that polygon with positive area always exists

Input

The input consists of multiple test cases.
The first line contains an integer $t$ $(1 \leq t \leq 100)$ — the number of test cases.
The first line of each test case contains an integer $n$ $(3 \leq n \leq 100)$ — the number of people in Winden.
Each of the next $n$ lines contains two integers $x, y$ $(−10^{9} \leq x,y \leq 10^{9})$ — the coordinates of the people in Winden.

Output

For each test case print the minimum positive polygon area of a subset of the given coordinates. Your answer will be considered correct if its absolute or relative error doesn’t exceed $10^{-4}$.

Sample

InputOutput
2
4
0 0
0 1
1 1
2 2
4
0 0
0 3
1 2
2 2
0.5000000000
0.5000000000

    Discussion

    Statistics


    72% Solution Ratio

    dUfReSnEEarliest, 2w ago

    serotoninFastest, 0.0s

    dUfReSnELightest, 131 kB

    deshchow.00Shortest, 690B

    Submit

    Login to submit