| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1043
Jack's Cow Shed
Time Limit: 1000ms
Memory Limit: 65536kb Description
Jack owns a piece of farm field with some trees on it. He wants to build a cow shed on his farm. Here is his plan: 1. The shape of the cow shed is a triangle. There should be a tree at each vertex of the triangle. 2. There is a tree at the center of the farm field. Jack has chosen this tree to be a vertex of the triangle. 3. No tree could be inside the triangle or on the edges of the triangle. (Except the three trees at the three vertices) 4. The area of the cow shed should be as large as possible. What is the maximum area of Jack's cow shed? Input
There are at most 20 test cases. Each case begins with a line containing an integer N (3<=N<=500). There are N lines following. Each line contains two integers Xi,Yi (-1000 <= Xi,Yi <= 1000) indicating the X and Y coordinates of the i-th tree. No two trees are at the same place. The tree chosen by Jack is the first tree. It is always located at X1=0, Y1=0. A case with N=0 marks the end of input. This case should not be processed. Output
You have to print only one line for each test case. If a cow shed can be built, you should print the maximum area of the cow shed. Leave one digit after the decimal point. When it is impossible to build a cow shed with positive area, print "0.0" instead.
Sample Input
3 0 0 1 0 2 0 4 0 0 0 1 -1 9 4 28 5 0 0 1 0 -1 0 0 1 0 -1 0 Sample Output
0.0 2.0 0.5 |