题解 | 小红的平行四边形

#include <bits/stdc++.h>
using namespace std;

#define sc second
#define fr first
#define int long long
#define itn long long
#define for for
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define endl '\n'
#define all(qwq) qwq.begin(), qwq.end()
#define ui unordered_map<int, int>
#define pq priority_queue
#define pi acos(-1)
#define vq vector<qwq>

// const int dx[4] = {-1, 1, 0, 0};
// const int dy[4] = {0, 0, -1, 1};
// const int dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
// const int dy[8] = {1, 1, 1, 0, -1, -1, -1, 0};
// const int dx[12] = {-1, 0, 1, 1, 1, 0, -1, -1, 0, 2, -2, 0};
// const int dy[12] = {1, 1, 1, 0, -1, -1, -1, 0, 2, 0, 0, -2};
// const int mod = 998244353;
// const int mod = 1e9 + 7;

int m, n, k, x, y, l, r, num, op, sum, cnt;
string s, w;
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int ksm(int a, int b, int mod)
{
    int tmp = 1;
    while (b)
    {
        if (b & 1)
        {
            tmp = tmp * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return tmp;
}
struct qwq
{
    int sx, sy; // 中点坐标（由于只需比较，不除以2以保持整数）
    int dx, dy; // 向量分量，用于面积计算

    // 排序优先级：按中点坐标排序，方便分组
    bool operator<(const qwq &awa) const
    {
        if (sx != awa.sx)
            return sx < awa.sx;
        return sy < awa.sy;
    };
};

void _()
{
    cin >> n;
    vector<pii> p(n);
    for (int i = 0; i < n; i++)
        cin >> p[i].fr >> p[i].sc;

    vq res;
    // 1. 记录所有可能的对角线及其“中点”
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            // sx, sy 是中点坐标的两倍；dx, dy 是对角向量
            res.push_back({p[i].fr + p[j].fr, p[i].sc + p[j].sc, p[i].fr - p[j].fr, p[i].sc - p[j].sc});
        }
    }

    // 2. 将相同中点的线段放在一起
    sort(all(res));
    int ans = 0;
    // 3. 遍历每一组具有相同中点的线段
    for (int i = 0; i < res.size(); i++)
    {
        int j = i + 1;
        while (j < res.size() && res[j].sx == res[i].sx && res[j].sy == res[i].sy)
        {
            // 同一组内的任意两条线段均可构成平行四边形
            for (int k = i; k < j; k++)
            {
                // 面积 = 0.5 * |对角线向量1.x * 对角线向量2.y - 对角线向量1.y * 对角线向量2.x|
                int cur_area = abs(res[k].dx * res[j].dy - res[k].dy * res[j].dx);
                // 注意：由于对角线端点是整数，平行四边形面积必为偶数（此处未除以2是为保持精度）
                ans = max(ans, cur_area);
            }
            j++;
        }
        i = j - 1; // 跳过已处理的组
    }

    // 4. 输出结果
    if (ans == 0)
    {
        cout << -1 << endl;
    }
    else
    {
        // 由于 ans 是 2 * Area，所以输出 ans / 2 并补上 .0
        cout << ans / 2 << ".0" << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);
    int awa = 1;
    // cin >> awa;
    while (awa--)
    {
        _();
    }
    return 0;
}