Triangles

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 7.0s
Memory limit: 1G

Problem type

Given n points in a plane, find the triangles with the smallest and largest areas formed by any three of the points.

Constraints

3 \le n \le 2 \cdot 10^3

|x|, |y| \le 10^4

Input Specification

There will be several test cases in the input. Each test case will begin with an integer n on its own line, indicating the number of points. On each of the next n lines will be two integers x and y, representing a point. No test case will contain duplicate points. The input will end with a 0 on its own line.

Output Specification

For each case, output the areas of the smallest, then largest, triangles formed by any 3 of the points in the test case. Output these numbers with exactly one decimal place of accuracy, with exactly one space between them. Output no extra spaces, and do not separate answers with blank lines.

Sample Input

4
-5 -5
-4 3
4 1
3 -2
7
1 0
2 0
0 2
2 3
0 1
3 0
0 3
0

Sample Output

10.5 33.0
0.0 4.0

Comments

There are no comments at the moment.