# Practice on Toph

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

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

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 `$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.

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}$`

.

Input | Output |
---|---|

2 4 0 0 0 1 1 1 2 2 4 0 0 0 3 1 2 2 2 | 0.5000000000 0.5000000000 |

72% Solution Ratio

dUfReSnEEarliest,

serotoninFastest, 0.0s

dUfReSnELightest, 131 kB

deshchow.00Shortest, 690B

Login to submit