Largest and Smallest Triangle
Time limit6sMemory limit128 MB
Given n points in the plane, compute the largest and smallest areas among all triangles formed by triples of the points.
- Level
Hard9 of 10
- Topics
- Geometry, Sorting, Two pointers
- Solved
- No attempts yet
Problem
There are points on the plane. Any three of them span a triangle. Find the area of the largest such triangle and the area of the smallest one. If the three chosen points lie on a single line, the area of that triangle counts as .
Input
The input holds several test cases. The first line of each test case has the number of points (). Each of the next lines has two integers and (), the coordinates of one point. No point appears twice inside one test case. The last line of the input holds a single and is not a test case.
Output
For each test case print one line with two numbers: first the area of the smallest triangle, then the area of the largest triangle, separated by a space. Print both with exactly one digit after the decimal point. All coordinates are integers, so every area is a multiple of and one decimal digit is exact.