Description

在某块平面土地上有 \(n\) 个点, 你可以选择其中的任意四个点, 将这片土地围起来, 当然, 你希望这四个点围成的多边形面积最大.

Input

第 \(1\) 行一个正整数 \(n\), 接下来 \(n\) 行, 每行 \(2\) 个数 \(x, y\), 表示该点的横坐标 和纵坐标.

Output

最大的多边形面积, 答案精确到小数点后 \(3\) 位.

Sample Input

5
0 0
1 0
1 1
0 1
0.5 0.5

Sample Output

1.000

Data Range

保证:\(n \leq 2000, |x|, |y| \leq 10^5\)

Explanation

考虑每一条经过任意两个点的斜线, 我们如果令这个四边形中一定有这一条直线作为对角线, 那么必要地, 一定需要另外两个点离这两个点尽量远.

也就是说, 另外两个点一定在凸包上. 所以我们先用 Graham 维护出所有点构成的点阵的 凸包, 然后递归每一个对角线, 复杂度 \(O(n^2)\), 然后在均摊 \(O(1)\) 的时间内转移最佳 的 (上、下) 两个点. 这两个点与对角线构成一个四边形, 记一下面积就可以了.

这道题里面我写的随机访问栈在实际应用中还是很好用的, 另外还可以用负数来寻址, 在搞几何凸包的时候不知道高到哪里去了~ 这个概念是从 Python 那里借鉴过来的 233

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

#define sqr(__x) ((__x)*(__x))
using namespace std;
typedef long long lli;
typedef long double llf;
const int maxn = 2010;

template <typename _T>
class random_access_stack
{
private:
    // vector<_T> data;
    _T data[maxn];
    int a_size;
public:
    void pop() {
        // data.erase(--data.end());
        if (a_size > 0) a_size--;
        return ; }
    void push(_T in) {
        // data.push_back(in);
        data[++a_size] = in;
        return ; }
    _T& top(void) {
        // if (this->empty()) {
        //     _T* zero = new _T; return *zero; }
        // return *--data.end(); }
        return data[a_size]; }
    _T get(void) {
        // _T ret = this->top();
        // this->pop();
        // return ret; }
        return data[a_size--]; }
    bool empty(void) {
        // return data.empty(); }
        return a_size <= 0; }
    void clear(void) {
        a_size = 0; return ; }
    size_t size(void) {
        // return data.size(); }
        return a_size; }
    _T& operator[] (int pos) {
        // if (pos <= 0 || pos > this->size()) {
        //     _T* zero = new _T; return *zero; }
        // return data[pos - 1]; }
        if (pos <= -1) return data[a_size + 1 + pos];
        return data[pos]; }
};

struct coord { llf x, y;
    coord(llf _x, llf _y) { x = _x, y = _y; }
    coord(void) { x = 0, y = 0; } };
coord operator - (coord a, coord b) {
    return coord(a.x - b.x, a.y - b.y); }
llf operator * (coord a, coord b) {
    return a.x * b.y - a.y * b.x; }
llf dist(coord a, coord b) { // Not exactly distance, but its ^2.
    return sqr(a.x - b.x) + sqr(a.y - b.y); }

int n;
coord pnt[maxn];
random_access_stack<coord> stk;

bool cmp(coord a, coord b) {
    double perpendicular =
        (a - pnt[1]) * (b - pnt[1]);
    if (perpendicular == 0)
        return dist(a, pnt[1]) < dist(b, pnt[1]);
    return perpendicular < 0;
}

void eval_bounds(void)
{
    // Using Graham algorithm to evaluate this
    int select = 1; // Selected top-left point, top prioritized
    for (int i = 2; i <= n; i++)
        if (pnt[i].y < pnt[select].y || (pnt[i].y == pnt[select].y &&
                pnt[i].x < pnt[select].x))
            select = i;
    // Sorting these points according to slope
    swap(pnt[1], pnt[select]);
    sort(pnt + 2, pnt + n + 1, cmp);
    // Selecting points that composes the outer bounds of this geometry
    stk.clear();
    stk.push(pnt[1]); stk.push(pnt[2]);
    for (int i = 3; i <= n; i++) {
        while (stk.size() > 1 && (pnt[i] - stk[-2]) * (stk[-1] - stk[-2]) <= 0)
            stk.pop();
        stk.push(pnt[i]);
    }
    return ;
}

llf eval_result(void)
{
    stk.push(pnt[1]);
    llf res = 0;
    int m = stk.size() - 1;
    for (int x = 1; x <= m; x++) {
        int a = x % m + 1, b = (x + 2) % m + 1;
        // a is the top-point, whereas b serves the opposite.
        for (int y = x + 2; y <= m; y++) {
            while (a % m + 1 != y && (stk[y] - stk[x]) * (stk[a+1] - stk[x]) >
                    (stk[y] - stk[x]) * (stk[a] - stk[x]))
                a = a % m + 1;
            while (b % m + 1 != x && (stk[b+1] - stk[x]) * (stk[y] - stk[x])>
                    (stk[b] - stk[x]) * (stk[y] - stk[x]))
                b = b % m + 1;
            res = max(res, (stk[y] - stk[x]) * (stk[a] - stk[x]) + (stk[b] - stk[x]) * (stk[y] - stk[x]));
        }
    }
    return res;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%Lf%Lf", &pnt[i].x, &pnt[i].y);
    eval_bounds();
    llf result = eval_result() / 2.0;
    printf("%.3Lf\n", result);
    return 0;
}