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
Recommend
lcy
思路：
最大三角形的三个点一定在点的凸包上，求出凸包之后，直接暴力枚举点即可
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 55000;
const int INF = 0x3f3f3f3f;
const int eps = 1e-8;
int sgn(double x)//判断浮点数x的符号,0返回0，正数返回1，负数返回-1
{
if (fabs(x) < eps)return 0;
if (x < 0)return -1;
else return 1;
}
struct Point
{
int x, y;
Point() {}
Point(int _x, int _y)
{
x = _x; y = _y;
}
Point operator -(const Point &b)const
{
return Point(x - b.x, y - b.y);
} double operator ^(const Point &b)const //叉积
{
return x * b.y - y * b.x;
} double operator *(const Point &b)const //点积
{
return x * b.x + y * b.y;
}
bool operator ==(const Point &b)const
{
return (x == b.x) && (y == b.y);
}
bool operator !=(const Point&b)const
{
return (x != b.x) || (y != b.y);
}
void input() { //点的输入
scanf("%d%d", &x, &y);
}
};
struct Line {
Point s, e;
Line() {}
Line(Point _s, Point _e) {
s = _s; e = _e;
}
}; double dist(Point& a, Point& b) //*两点间距离
{
return sqrt((a - b) * (a - b));
}
Point zero;
int k;
bool cmp(Point& a, Point &b)
{
double tmp = (a - zero) ^ (b - zero);
if (sgn(tmp) > 0) {
return 1;
}
if (sgn(tmp) == 0 && sgn(dist(a, zero) - dist(b, zero)) <= 0)
return 1;
return 0;
}
int n;
Point a[MAXN];
int l[MAXN];
int cou = 0;
void Gram()
{
cou = 0;
swap(a[0], a[k]);
sort(a + 1, a + n, cmp);
if (n == 1) {
l[cou++] = 0;
return;
}
if (n == 2) {
l[cou++] = 0;
l[cou++] = 1;
return;
}
l[cou++] = 0;
l[cou++] = 1;
for (int i = 2; i < n; i++) {
while (sgn((a[i] - a[l[cou - 2]]) ^ (a[l[cou - 1]] - a[l[cou - 2]])) != -1) {
cou--;
}
l[cou++] = i;
}
}
int main()
{
//freopen("data.in", "r", stdin);
while (~scanf("%d", &n)) {
zero.x = zero.y = INF;
for (int i = 0; i < n; i++) {
a[i].input();
if (a[i].y < zero.y) {
zero.x = a[i].x;
zero.y = a[i].y;
k = i;
}
else if (a[i].y == zero.y) {
if (a[i].x < zero.x) {
zero.x = a[i].x;
zero.y = a[i].y;
k = i;
}
}
}
Gram();
double res = -3;
for (int i = 0; i < cou; i++) {
for (int j = 0; j < cou; j++) {
for (int k = 0; k < cou; k++) {
double tmp = fabs((a[l[i]] - a[l[j]]) ^ (a[l[k]] - a[l[j]]));
if (tmp > res) {
res = tmp;
}
}
}
}
res = res / 2 ;
printf("%.2lf\n", res);
}
}