给出点集,求这个点集所组成的三角形的面积最大。

考虑旋转卡壳。~~选择凸包的边，然后选择卡壳求最大的高。~~

显然这是错的，因为高的最高，但是底边不一定最大。

首先点一定是凸包上的点，尽量的扩大。枚举一个固定点$x$，然后调整两个点$p1,p2$。首先固定$x-p1$找到最高点$p2$，再固定$x-p2$找到最高点$p1$，可以证明是最优。然后由于旋转卡壳性质把（可能）$p1,p2$都是一个方向游走的。

代码

```c++

include

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int pos;
struct point
{
int x, y;
double v, li;
point operator-(const point &p) const { return (point){x - p.x, y - p.y}; };
point operator+(const point &p) const { return (point){x + p.x, y + p.y}; };
int operator^(const point &p) const { return x p.y - y p.x; };
int operator(const point &p) const { return x p.x + y p.y; };
double dis() const { return sqrt(x x + y y); }
int dis2() const { return x x + y y; }
} p[N];
int eare(point p1, point p2, point p3)
{
point p4 = p2 - p1;
point p5 = p3 - p1;
return abs(p4 ^ p5);
}
vector g;
bool cmp(point p1, point p2)
{
p1 = p1 - g[pos];
p2 = p2 - g[pos];
return ((p1 ^ p2) == 0 ? (p1 p1) < (p2 * p2) : (p1 ^ p2) > 0);
}
point s[N];
int top;
double graham()
{
if (g.size() == 1)
return 0;
for (int i = 1; i < g.size(); i++)
if (g[i].y < g[0].y || (g[i].y == g[0].y && g[i].x < g[0].x))
swap(g[0], g[i]);
pos = 0;
sort(g.begin() + 1, g.end(), cmp);

top = -1;
s[++top] = g[0];
for (int i = 1; i < g.size(); i++)
{
    while (top && ((g[i] - s[top]) ^ (s[top] - s[top - 1])) >= 0)
        top--;
    s[++top] = g[i];
}
s[top + 1] = g[0];
double ans = 0;
for (int i = 1; i <= top; i++)
    ans += (s[i] - s[i + 1]).dis();
return ans;

}
int getmmx()
{
int res = 0;
if (top == 1)
return 0;
s[++top] = s[0];
int t1 = 1, t2 = 2;
for (int i = 0; i < top; i++)
{
while (eare(s[i], s[t1], s[t2]) < eare(s[i], s[t1], s[(t2 + 1) % top]))
t2 = (t2 + 1) % top;
while (eare(s[i], s[t1], s[t2]) < eare(s[i], s[(t1 + 1) % top], s[t2]))
t1 = (t1 + 1) % top;

    res = max(res, eare(s[i], s[t1], s[t2]));
}
return res;

}
int n;
int main()
{

while (scanf("%d", &n))
{
    if (n == -1)
        break;

    g.clear();

    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &p[i].x, &p[i].y);
        g.push_back(p[i]);
    }
    graham();
    printf("%.2f\n", 1.0 * getmmx() / 2.0);
}

}