点击打开hdu2202
思路：最大三角形面积，那么肯定这三个点在最外围，所以先求凸包，然后用旋转卡壳求出那三个点求出面积最大。
#include <iostream>
#include <algorithm>
#include <iomanip>
#include<stdio.h>
using namespace std;
const int maxn = 50010;
struct Point {int x , y;bool operator < (Point const &rhs) const {return (x < rhs.x) || (x == rhs.x && y < rhs.y);}
};int Cross(Point const &O , Point const &A , Point const &B)
{int xoa = A.x - O.x;int xob = B.x - O.x;int yoa = A.y - O.y;int yob = B.y - O.y;return xoa * yob - xob * yoa;
}
int Andrew(Point *p , int n , Point *ch)
{sort(p , p + n);int m = 0;for(int i = 0; i < n; i++){ //下凸包while(m > 1 && Cross(ch[m-2] , ch[m-1] , p[i]) < 0) m--;ch[m++] = p[i];}int k = m;for(int i = n - 2; i >= 0; i--) { //上凸包while(m > k && Cross(ch[m-2] , ch[m-1] , p[i]) < 0) m--;ch[m++] = p[i];}if(n > 1) m--;return m;
}
Point p[maxn] , ch[maxn];
int main()
{int n;while(cin >> n){for(int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;int m = Andrew(p , n , ch); ///求凸包///旋转卡壳法int ans = 0;for(int i = 0; i < m; i++){int q = 1;for(int j = i + 1; j < m; j++){while(Cross(ch[i],ch[j],ch[q+1]) > Cross(ch[i],ch[j],ch[q]))q = (q + 1) % m;ans = max(ans , Cross(ch[i],ch[j],ch[q]));}}//cout << fixed << setprecision(2) << ans / 2.0 << endl;printf("%.2lf\n",ans/2.0);}return 0;
}