DRAWQUAD - Drawing Quadrilaterals

no tags 

A quadrilateral consists of 4 points A, B, C and D in the plane, together with the
segments AB, BC, CD and DA. Points are called vertices, while segments are called
sides. The quadrilateral is simple if opposite sides (i.e., sides that do not share a vertex)
do not intersect. Notice that it is possible to have a simple quadrilateral that looks like
a triangle, with exactly 3 collinear vertices.
Demetrio has just drawn N points on the wall of his room. He planned to draw a
simple quadrilateral having 4 of these points as vertices, and then paint it with blue ink.
Demetrio is going to buy the ink right now, but he has not chosen the 4 points yet. Can
you tell him the maximum area a simple quadrilateral drawn on his wall can have? In
this way Demetrio will be sure he will not run out of blue ink before the work is done.

Input

Each test case is described using several lines. The first line contains an integer N
indicating the number of points drawn on the wall (4 ≤ N ≤ 1000). Each of the next N
lines describes a different point of the set using two integers X and Y (−107 ≤ X, Y ≤
107 ); these values represent the coordinates of the point in the XY plane. You may
assume that within each test case no two points have the same location, neither are all
collinear. The end of input is indicated with a line containing a single −1.

Output

For each test case, output a single line with a single decimal number representing the
maximum area of a simple quadrilateral having as vertices 4 different points of the input
set. Round the result to the closest rational number with one decimal place. In case of
ties, round up. Always use exactly one digit after the decimal point, even if it means
finishing with a zero.

Example

Input: 
6
-100 0
100 0
-100 50
0 55
0 -65
1 1
4
-1 0
10000 0
0 0
0 1
-1 Output:
12000.0
5000.5

hide comments
Srijith Balachander: 2016-11-05 10:58:36

Can somebody tell a corner case that this will fail? I have tried everything but I think I am missing something trivial. I have already submitted a lot of times. I am advancing four points that keep track of the quadrilateral formed and so on.
Thank you.

Termvader: 2012-12-01 09:02:00

I have a doubt, If there are only 4 points and they form a concave quadrilateral, what will be the answer:
lets say for input
4
0 2
2 -2
-2 -2
-1 -1
-1
the answer will be 8.0 (area of the convex triangle)
or will it be 7.0 (area of the concave quadrilateral)

EDIT: it will be 7.0

Last edit: 2012-12-01 12:14:22

Added by:Pablo Ariel Heiber
Date:2010-09-26
Time limit:6.986s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC VB.NET
Resource:FCEyN UBA ICPC Selection 2010