A survey crew has driven marker stakes into a flat parcel of land at n integer grid coordinates. To carve out the single largest triangular sub-plot they can stake out for a client, they may pick any three of the planted stakes as its corners. Determine the area of the largest such triangle obtainable from any three of the stakes.
The first line contains a single integer n, the number of stakes. Each of the next n lines contains two integers x and y, the coordinates of one stake.
Print the maximum triangle area obtainable from any three of the n stakes, formatted with exactly 5 digits after the decimal point. Three collinear stakes form a degenerate triangle of area 0.00000 and are a legal (if suboptimal) choice.
3 <= n <= 50-50 <= x, y <= 50Example 1
Input
3 0 0 0 1 1 0
Expected
0.50000
Explanation
Only one triangle can be formed from the three stakes: (0,0), (0,1), (1,0). It is a right triangle with two perpendicular legs of length 1 each, so its area is 0.5 * 1 * 1 = 0.50000.
Example 2
Input
4 0 0 0 1 1 0 0 2
Expected
1.00000
Explanation
Checking all four possible triples, the pair (0,0) and (0,2) forms a vertical base of length 2 along the y-axis, and the stake (1,0) sits at horizontal distance 1 from that line, giving area 0.5 * 2 * 1 = 1.00000. Every other triple (e.g. (0,0),(0,1),(1,0) or (0,1),(1,0),(0,2)) yields only area 0.50000, so the maximum is 1.00000.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →