Submit solution

Points:
15 (partial)

Time limit:
1.0s

Memory limit:
256M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, ~~CommonLisp~~, D, Dart, F#, Forth, Fortran, Go, ~~Groovy~~, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ~~Nim~~, ~~ObjC~~, OCaml, ~~Octave~~, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Given points with coordinates , determine the largest possible area of a triangle formed by three of these points.

#### Constraints

For all subtasks,

for all

All coordinates are guaranteed to be distinct.

##### Subtask 1 [30%]

##### Subtask 2 [70%]

#### Input Specification

The first line will contain a single integer, .

The next lines will each contain two space separated integers and , the coordinates of the point.

#### Output Specification

Output a single number, the largest possible area. Your answer will be judged as correct if your area has an absolute error of no more than .

#### Sample Input 1

```
7
2 13
5 5
-6 3
0 0
7 10
-8 4
2 3
```

#### Sample Output 1

`56.000`

#### Sample Input 2

```
3
1 5
4 5
7 5
```

#### Sample Output 2

`0.000`

## Comments

A word of warning to those who use the well-known rotating callipers solution for this problem: it turns out that this solution is incorrect. I have added a few more test cases to try to hack this solution (although I will not rejudge already accepted solutions). For further details about this, see here.

I just use three loops for all points on the convex hull and got AC.

The judges were replaced with much faster ones, so it looks like we will need to adjust the time limit.

This comment is hidden due to too much negative feedback. Click here to view it.

Just use Heron's formula and three loops!

You don't have to use Heron's formula. Given three points will give you the area of the triangle defined by these points.

In theory, that should only pass the first subtask. Though the bounds might not be strong enough to prevent that solution from passing...

Can you give me a hint on how to pass the second subtask?

Good point! I passed the first batch, but I got TLE on the second.