oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

land Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

land.html

Problem Description

You have N points on a plot of land. You are allowed to select up to 4 points and fence up the area contained within the selected points. However, you are greedy and want to maximize the largest area you can have. Find out what is this maximum area!

Input

First line of input contains an integer, N.

Following N lines will have 2 floating point values each, the X and Y co-ordinates of each point respectively.

Please use double type floating point (or higher precision) to input the co-ordinates.

Output

The maximum possible area contained within up to 4 of the N points. Print your answer to 3 decimal places.

Limits

For all testcases, -105 ≤ X, Y ≤ 105.

Subtask 1 (30%): 4 ≤ N ≤ 50.

Subtask 2 (20%): 4 ≤ N ≤ 1000. In addition, the points are randomly distributed in an uniform manner.

Subtask 3 (50%): 4 ≤ N ≤ 2000.

Subtask 4 (0%): Sample Testcases.

Sample Testcase

Input

5
0 0
1 0
1 1
0 1
0.5 0.5

Output

1.000

Tags

SCOI 2007

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
13040.5s128MBMinimum
22060.5s128MBMinimum
350110.5s128MBMinimum
4010.5s128MBMinimum

Judge Compile Command

g++-8 ans.cpp -o land -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.