DMPG '18 G5 - Triangles

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
r3mark
Problem type

Given 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 points.

Constraints

For all subtasks:

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

All coordinates are guaranteed to be distinct.

Subtask 1 [30%]

3 \le N \le 500

Subtask 2 [70%]

3 \le N \le 4\,000

Input Specification

The first line will contain a single integer, N.
The next N lines will each contain two space separated integers x_i and y_i, the coordinates of the 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}.

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


  • 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) 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_1,y_1), (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.