This page is still under construction.

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

Fortress Construction

Time limit7sMemory limit256 MB

Summary
Choose up to four of the given points as corners of a convex polygon with maximum area.
Level

Medium6 of 10

Topics
Geometry, Brute force
Solved
No attempts yet

Problem

At most four watchtowers may be placed on given candidate points. Find the maximum area of a convex base whose corners are chosen from those points.

Input

The first line contains TT. Each test gives nn distinct points.

Output

Print the maximum base area. Use one decimal place only when the area is half-integer.

Examples1

  1. Example 1

    Input
    3
6
0 0
3 7
10 0
11 6
0 10
10 10
5
0 0
-2 -2
3 -2
0 1
0 3
10
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 3
2 3
8 4
    Expected output
    100
12.5
31