## DMPG '18 G5 - Triangles

View as PDF

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
All coordinates are guaranteed to be distinct.

#### 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

• commented on Aug. 20, 2018, 1:04 p.m.

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.

• commented on March 9, 2020, 6:20 a.m.

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

• commented on March 9, 2020, 1:33 p.m.

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

• commented on April 29, 2018, 11:51 p.m. edited

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

• commented on April 29, 2018, 3:03 p.m.

Just use Heron's formula and three loops!

• commented on March 9, 2020, 5:11 a.m. edit 3

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

• commented on April 29, 2018, 3:06 p.m.

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

• commented on April 30, 2018, 12:33 a.m.

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

• commented on April 29, 2018, 11:39 p.m.

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