Johny the farmer

Problem code: E3

All submissions for this problem are available.

Johny the Farmer has decided to plant potatoes. He quickly realized that he must build a net fence to keep animals from eating his precious plantation. But he only has 3 sticks which can act as vertical poles supporting fence; on the other hand, his supply of net is unlimited. Moreover, since the ground is extremely rocky, the poles can only be positioned in some special places on the field. So, he has decided that the fence must be triangular in shape, with vertices in the distinguished points. Quite naturally, he would also like to maximize the area of the field inside fence -- please help him achieve this goal!

Task

Write a program which:

  • reads from the input the coordinates of the points which can hold the poles,
  • calculates the maximal possible area of the potato plantation.

Input

First, an integer t, representing the number of test cases.

Each test case starts with an integer n (n 106). In each of the next n lines there is pair of integers separated by spaces, xi, yi, which are the coordinates for i-th point where a pole can potentially be located (0 xi,yi 10000).

Output

For each test case output a single integer - the area of the field surrounded by the fence, multiplied by 2.

Example

Input
1
5
0 0
1 0 
0 1
1 2
1 1

Output
2
Author: admin
Date Added: 5-06-2009
Time Limit: 1 - 7 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

hrj @ 2 Jul 2009 03:43 AM

So, the output should be rounded, ceilinged / floored ?

hrj @ 2 Jul 2009 05:50 AM

Ok, so my first submission failed as TLE.

So I tried a dummy submission, which only reads the test input and doesn't even process it. Even THAT fails with TLE. Something wrong here?

dgreensp @ 2 Jul 2009 07:59 AM

My latest two Scala submissions returned with "internal error" after 8 minutes of compilation. Is your Scala compiler down?

On the subject of exceeding the time limit, reading in a million points efficiently on the JVM requires some care. By doing it at the byte stream level, I can read in a million points in about 100ms, and process them in less (on my laptop, at least). If that's not fast enough, then I'll have to port my code to C, which would be very sad.

aforarup @ 2 Jul 2009 03:51 PM

my submission runs first class in my Turbo C compiler... but failing in yours...!!! why?

i0exception @ 2 Jul 2009 05:18 PM

@Harshad Make sure your IO is fast enough to clear the Problem "The enormous input test" in the easy section of the practice problems.

@Anomymous Will look into the Scala compiler thing. Also, I believe the time limit for Java is 2x the time limit for C/C

@Arup Turbo C is a non standard compiler. Frankly, it is outdated. Please read the FAQ to see what compilers we are using.

sankalan @ 2 Jul 2009 08:48 PM

why should i multiply it by 2??

i0exception @ 2 Jul 2009 09:43 PM

@sarker Because the problem statement says so.

aditi23 @ 2 Jul 2009 10:01 PM

Aaarrgghhhh ... you changed the format of the input ..... :(

hrj @ 3 Jul 2009 02:30 AM

@Aniruddha Yup the "enormous input test" fails. Can't figure out why!

Copying my comment from there:

My scala program given a test with n = 10^6 runs under 3 seconds on my laptop (Core 2 Duo, 1.6Ghz)

Why would it timeout on your servers?

mohitkanwal @ 3 Jul 2009 05:15 AM

any ideas why does I get sigsegv in cpp and nzec in pascal

i hv read the FAQs ... doesn't help still..

akskap @ 3 Jul 2009 06:35 PM

We need to find out the best combination of three points per test case that would ensure maximum area covered.. Rite ?

admin 2 @ 3 Jul 2009 06:49 PM

@akshay Yes.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions