DMPG '18 G5 - Triangles - Olympiads Online Judge

DMPG '18 G5 - Triangles

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

r3mark

Problem type

Given $N$ $N$ points with coordinates $(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)$ $(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} | \leq 10 000$ for all $1 \le i \le N$ $1 \leq i \leq N$ .

All coordinates are guaranteed to be distinct.

Subtask 1 [30%]

$3 \le N \le 500$ $3 \leq N \leq 500$

Subtask 2 [70%]

$3 \le N \le 4\,000$ $3 \leq N \leq 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^{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

Copy

Sample Output 1

Copy

56.000

Sample Input 2

Copy

Sample Output 2

Copy

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)$ $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))$ $\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.