凸包旋轉卡殼求最大三角形面積
最大三角形
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3316 Accepted Submission(s): 1119
Problem Description
老師在計算幾何這門課上給Eddy布置了一道題目,題目是這樣的:給定二維的平面上n個不同的點,要求在這些點裡尋找三個點,使他們構成的三角形擁有的面積最大。
Eddy對這道題目百思不得其解,想不通用什麼方法來解決,因此他找到了聰明的你,請你幫他解決這個題目。
Input
輸入數據包含多組測試用例,每個測試用例的第一行包含一個整數n,表示一共有n個互不相同的點,接下來的n行每行包含2個整數xi,yi,表示平面上第i個點的x與y坐標。你可以認為:3 <= n <= 50000 而且 -10000 <= xi, yi <= 10000.
Output
對於每一組測試數據,請輸出構成的最大的三角形的面積,結果保留兩位小數。
每組輸出占一行。
Sample Input
3
3 4
2 6
3 7
6
2 6
3 9
2 0
8 0
6 6
7 7
Sample Output
1.50
27.00
Author
Eddy
/* ***********************************************
Author :CKboss
Created Time :2014年12月28日 星期日 19時28分15秒
File Name :HDOJ2202.cpp
************************************************ */
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include