MTRIAREA - Maximum Triangle Area

no tags 

 

Cho n điểm trên mặt phẳng. Tìm tam giác có diện tích lớn nhất tạo được từ n điểm này.

 

Input

 

Gồm một vài test case. Dòng đầu của mỗi test là số nguyên n, số điểm trên mặt phẳng. Mỗi dòng tiếp theo mỗi dòng chứa hai số nguyên xi, yi là tọa độ điểm thứ i. Kết thúc các bộ test là số -1. Chú ý 1 ≤ n ≤ 50000 và −10^4 ≤ xi, yi ≤ 10^4 với i = 1 . . . n.

Sample Input
3
3 4
2 6
2 7
5
2 6
3 9
2 0
8 0
6 5
-1

Output

 

In ra trên mỗi dòng là diện tích lớn nhất của mỗi test, gồm 2 số thập phân sau dấu phẩy.

Sample output
0.50
27.00


hide comments
eagle93: 2017-12-21 12:23:15

weak test cases:
please add the following test case:
9
4752 4262
3383 413
759 2927
4745 4322
1213 691
2506 4423
3040 4460
1000 1000
5000 1000
9
2459 691
2828 758
4361 1951
4183 4244
3832 4647
2529 5756
2481 5718
0 3587
728 2028
-1
the correct output is:
6920000.00
6919204.00

arjundabra: 2016-06-25 13:37:38

Those getting wrong answer should print exactly two digits after the decimal point.

anhkhoa: 2016-05-20 11:40:36

that sample output should be 1.50 and 15.00, right ?

Naman Goyal: 2014-07-26 10:57:21

Don't use float, you'll get WA.

hit_code: 2014-06-13 17:57:17

some more test case?

:D: 2012-11-16 07:10:37

Yes, they seem to rule each other out. Well, strictly speaking 1 <= n <= 50000, doesn't require some n to be 1 or 2, but ranges shouldn't be that unnecessary invalid.

uberness132: 2012-11-16 03:13:50

how can n < 3? "You may assume that 1 ≤ n ≤ 50000 " and "You may assume that there is always an answer which is greater than zero."

Cong Liu: 2010-11-24 09:46:44

My algo is O(n) which I think should be right but not yet proofed.

Last edit: 2009-04-15 15:01:38
[Trichromatic] XilinX: 2010-11-24 09:46:44

O(n^2)(Of course, with many optimizations) CAN get Accepted!

Last edit: 2009-03-26 03:01:49

Added by:~!(*(@*!@^&
Date:2009-02-23
Time limit:0.170s-0.712s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO PERL6
Resource:Pre Shanghai 2004