题解：P11548 [BalticOI 2009] 矩形 (Day2)

· · 题解

前置知识

确定两点后，如果另外两点的连线和这两点的连线的长度和中心点都相等。那么这四个点可以组成一个矩形，且前两点连的线段和后两点连的线段是矩形的对角线。

思路

O(n ^ 4) 复杂度的暴力

最暴力的暴力，直接枚举四个点，然后看这四个点可以不可以组成矩形，如果可以就计算一下，最后统计最大值。

O(n^4) 复杂度的暴力

这个方法虽然复杂度基本上没变化，但是有优化的余地。

枚举任意两点组成对角线，然后枚举任意两条对角线，如果这两个对角线的长度相等，而且线段的中心重合，那么就可以组成一个矩形。具体计算方法和之前相同。

O(n^2\log(n^2)) 复杂度的正解

我们发现，枚举出一条对角线后，不一定要枚举第二条对角线。因为第二条符合要求的对角线一定和第一条对角线的长度相同，而且中心点的横纵坐标相同。由此，我们可以想到通过排序来解决。

先枚举任意两点找到所有对角线，然后以对角线长度为的第一关键字，对角线的中心的横纵坐标为第二第三关键字。排完序后的对角线数组满足一个规律，就是每次遍历到一个对角线，然后往后遍历的时候，如果有一个对角线的长度或者中心点都不匹配，那么后面绝对不会再遇到匹配的，而且遍历开始的那一条对角线到临界的对角线中间的这一部分都是可以互相匹配的。

由此，我们就可以先枚举对角线，然后排序，然后再遍历这个对角线。虽然上面的文字看起来需要双重循环，但是有一个小小的优化。就是每次遍历到一个临界值后，通过上面的性质，在这一个集合的点两两配对计算后第一轮循环就可以直接跳过这个集合。

而且我们还可以证明，如果 n 个点共圆，那么对角线只有 \frac{n}{2} 条，不会超时。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ldo long double 
int n;
int x[1000005], y[1000005], cnt;
struct Edge {
    int x, y, i, j;
    ldo len;
} a[3000005];
bool cmp(Edge x, Edge y) {
    if (x.len != y.len) return x.len > y.len;
    if (x.x != y.x) return x.x < y.x;
    return x.y < y.y;
}
ldo leng(int i, int j) {
    return ((x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i]));
}
void add(int i, int j) {
    a[++cnt].len = leng(i, j);
    a[cnt].x = (x[i] + x[j]);
    a[cnt].y = (y[i] + y[j]);
    a[cnt].i = i; a[cnt].j = j;
}
signed main() {
    ios::sync_with_stdio(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> x[i] >> y[i];
    for (int i = 1; i <= n; i ++) {
        for (int j = i + 1; j <= n; j ++) {
            add(i, j);
        }
    }
    sort(a + 1, a + cnt + 1, cmp);
    int maxn = 0;
//  for (int i = 1; i <= cnt; i ++) {
//      cout << a[i].len << " " << a[i].x << " " << a[i].y << " " << a[i].i << " " << a[i].j << "\n";
//  }
    for (int i = 1; i <= cnt; i ++) {
        int last = i;
        while (abs(a[i + 1].len - a[i].len) == 0 && a[i + 1].x == a[i].x && a[i + 1].y == a[i].y) {
            for (int j = last; j <= i; j ++) {
                int S = 0;
                ldo Sa = sqrt(leng(a[j].i, a[i + 1].i));
                ldo Sb = sqrt(leng(a[j].j, a[i + 1].i));
                S = round(Sa * Sb);
                maxn = max(maxn, S);
            }
            i ++;
        }
    }
    cout << (int)maxn;
}
/*
8
-2 3
-2 -1
0 3
0 -1
1 -1
2 1 
-3 1 
-2 1

*/