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


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


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 10410^{-4}.


0 0
0 1
1 1
2 2
0 0
0 3
1 2
2 2



    74% Solution Ratio

    dUfReSnEEarliest, Jul '20

    serotoninFastest, 0.0s

    dUfReSnELightest, 131 kB

    blizzardShortest, 672B


    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.