DMPG '18 G5 - Triangles - DMOJ: Modern Online Judge

DMPG '18 G5 - Triangles

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

Given $N$ ~N~ points with coordinates $(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)$ , determine the largest possible area of a triangle formed by three of these $N$ ~N~ points.

Constraints

For all subtasks:

$|x_i|, |y_i| \le 10\,000$ ~|x_i|, |y_i| \le 10\,000~ for all $1 \le i \le N$ ~1 \le i \le N~.

All coordinates are guaranteed to be distinct.

Subtask 1 [30%]

$3 \le N \le 500$ ~3 \le N \le 500~

Subtask 2 [70%]

$3 \le N \le 4\,000$ ~3 \le N \le 4\,000~

Input Specification

The first line will contain a single integer, $N$ ~N~.
The next $N$ ~N~ lines will each contain two space separated integers $x_i$ ~x_i~ and $y_i$ ~y_i~, the coordinates of the $i^\text{th}$ ~i^\text{th}~ 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 $10^{-3}$ ~10^{-3}~.

Sample Input 1

Sample Output 1

56.000

Sample Input 2

Sample Output 2

0.000

Comments

4

r3mark commented on Aug. 20, 2018, 5:04 p.m.

A word of warning to those who use the well-known $\mathcal{O}(N)$ ~\mathcal{O}(N)~ 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.

-1

harry7557558 commented on March 9, 2020, 10:20 a.m.

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

3

Kirito commented on March 9, 2020, 5:33 p.m.

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

-3

DarthVader336 commented on April 29, 2018, 7:03 p.m.

Just use Heron's formula and three loops!

1

harry7557558 commented on March 9, 2020, 9:11 a.m. ← edit 4 →

You don't have to use Heron's formula. Given three points $(x_0,y_0)$ ~(x_0,y_0)~, $(x_1,y_1)$ ~(x_1,y_1)~, $(x_2,y_2)$ ~(x_2,y_2)~, $\frac{1}{2}((x_1-x_0)(y_2-y_0)-(x_2-x_0)(y_1-y_0))$ will give you the area of the triangle defined by these points.

1

wleung_bvg commented on April 29, 2018, 7: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...

-4

DarthVader336 commented on April 30, 2018, 4:33 a.m.

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

-2

DarthVader336 commented on April 30, 2018, 3:39 a.m.

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