3603 - Rack

Created by Reinier Rodríguez González
Added by Spartan (2016-04-07)
Limits
Total Time: 9000 MS | Test Time: 3000 MS |Memory: 512 MB | Output: 64 MB | Size: 39 KB
Enabled languages
Available in

Description

A rack (sometimes known as a triangle) is the name given to a frame (usually wood, plastic or metal) used to organize billiard balls at the beginning of a game. In this problem you have to do the same job of a rack.

Given a set of points, could you calculate the area of the minimal enclosing triangle. In other words, could you calculate the area of the triangle, with the minimum area, that encloses all the points. A point lying on the edge of a triangle, is considered to be inside this.
A rack (sometimes known as a triangle) is the name given to a frame (usually wood, plastic or metal) used to organize billiard balls at the beginning of a game. In this problem you have to do the same job of a rack.

Given a set of points, could you calculate the area of the minimal enclosing triangle. In other words, could you calculate the area of the triangle, with the minimum area, that encloses all the points. A point lying on the edge of a triangle, is considered to be inside this.
A rack (sometimes known as a triangle) is the name given to a frame (usually wood, plastic or metal) used to organize billiard balls at the beginning of a game. In this problem you have to do the same job of a rack.

Given a set of points, could you calculate the area of the minimal enclosing triangle. In other words, could you calculate the area of the triangle, with the minimum area, that encloses all the points. A point lying on the edge of a triangle, is considered to be inside this.

Input specification

On the first line will be N ( 3 <= N <= 100 000 ), the amount of points. Then, N lines will follow. Each with two positive integer numbers, equal or less than 3000, the coordinates of each of the N points. No two points will have the same coordinates.
On the first line will be N ( 3 <= N <= 100 000 ), the amount of points. Then, N lines will follow. Each with two positive integer numbers, equal or less than 3000, the coordinates of each of the N points. No two points will have the same coordinates.
On the first line will be N ( 3 <= N <= 100 000 ), the amount of points. Then, N lines will follow. Each with two positive integer numbers, equal or less than 3000, the coordinates of each of the N points. No two points will have the same coordinates.

Output specification

You must print the area of the minimum enclosing triangle, rounded to 3 decimal ciphers.
You must print the area of the minimum enclosing triangle, rounded to 3 decimal ciphers.
On the first line will be N ( 3 <= N <= 100 000 ), the amount of points. Then, N lines will follow. Each with two positive integer numbers, equal or less than 3000, the coordinates of each of the N points. No two points will have the same coordinates.

Sample input

5
300 700
400 480
643 200
800 1100
1202 1005

Sample output

555408.394

Hint(s)

http://coj.uci.cu/contest/
http://coj.uci.cu/contest/
http://coj.uci.cu/contest/