2289. The Largest Triangle From Given Points
n points are given. Over all ways of choosing three of them, print TWICE the
largest area a triangle can have.
(0,0) (4,0) (0,3) -> 12
(0,0) (4,0) (4,4) (0,4) -> 16 half the square, either way round
(0,0) (1,0) (2,0) -> 0 every triple is collinear
## What most people try first
Picking the three points that are farthest apart from each other. It sounds
right and it is false. Take (0,0), (100,0), (50,1) and (50,-1). The two
farthest-apart points are (0,0) and (100,0); the pair of points farthest
apart after that is (50,1) and (50,-1), and a triangle has to drop one of
them. Maximising pairwise distances does not maximise an area, because an area
depends on a base and a HEIGHT, and a long third side can come with almost no
height at all.
The second instinct is to compute each triangle's area from its three side lengths. Those lengths are square roots, so that is the point where the answer stops being exactly comparable.
## Twice the area, straight from a cross product
For three points a, b, c:
2 * area = | (bx - ax) * (cy - ay) - (by - ay) * (cx - ax) |
an integer, so two candidate triangles can be compared exactly with a single
> and no tolerance. Take the largest over all n * (n-1) * (n-2) / 6 triples.
With n up to 300 that is at most 4455100 triples and a handful of
multiplications each, which is the intended cost. The bound is small on purpose:
the sub-cubic method relies on the fact that a largest-area triangle always has
all three vertices on the convex hull, and then rotates two pointers around it,
which is a different and much longer problem.
## What the answer is when there is no triangle
If every triple is collinear, every cross product is zero and the answer is 0.
That includes the case where all the points coincide. The maximum starts at 0
and nothing can lower it, so no special case is needed, which is another reason
to compare doubled areas rather than side lengths: a degenerate triple would
make a side-length formula take the square root of zero through a subtraction
that can round negative.
## Width
Coordinates satisfy |x|, |y| <= 1000000, so each difference is at most
2 * 10^6 and the cross product at most 8 * 10^12 in magnitude. A signed
32-bit integer stops at 2147483647, so a 32-bit build does not merely report a
wrong number, it compares two wrapped values and picks the wrong TRIANGLE. The
value is below 2^53 = 9007199254740992, so a JavaScript Number is exact and
no BigInt is needed.
Constraints - `3 <= n <= 300` - `-1000000 <= x, y <= 1000000` - points need not be distinct
Input
The first line contains an integer n.
Each of the next n lines contains two integers x y, one point.
Output
Print one integer, twice the largest triangle area achievable by three of the given points, alone on a line. Print 0 if every triple is collinear.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.