P1959 题解

· · 题解

突然发现这道题还可以发题解就过来水了。

思路

这道题的数据范围是 n \leq 3000，所以需用复杂度 \operatorname{O}(n^2) 的算法。

这样很容易想到一种方法：枚举其中两个点的位置，然后算出最大的面积。

也就是说，需要利用两个点的坐标确定另外两个点的坐标以判断是否存在这样的正方形，然后再算出正方形的面积。

关键在于：如何确定正方形并求出另外两个点的坐标？

两点可以确定一条直线，但确定边的位置的话会有两种情况，正方形可能在邻边两侧。这样做虽说完全可以，但还是麻烦了一些。

而两个点之间的连线可能是正方形的边，也有可能是对角线。于是我们可以想到，可以确定正方形的对角线，即确定对角的位置，由于对称性，两个正方形重合，于是我们可以认为确定了一个正方形。

接下来就是推坐标的计算公式。

直接求坐标似乎有点难度，于是我们可以作一个边与 x,y 轴平行的正方形辅助计算坐标，如下图。

于是我们用坐标差求出辅助的正方形的边长，以及上面某些线段的长度，由于这些线段与 x,y 轴平行，即可以由此算出另外两个点的坐标，公式可见图片。

但不仅有这一种作图方式的可能。

如果是其他方向的话，这里的公式仍然适用，只不过某些长度带的是负值。

数据范围是 x_i,y_i \leq 5000，可以直接开一个 bool 数组记录是否存在该点。

于是我们可以根据公式算出另两点的位置，并判断是否存在该两点。

于是判断完后，若符合条件，则只需算出正方形的面积。

这里确定了对角线，则可以求出对角线的长度 |l|=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}。

那么正方形的面积即为 \dfrac{|l|^2}{2}=\dfrac{(x_2-x_1)^2+(y_2-y_1)^2}{2}。

代码

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

int n, x[3333], y[3333], ans;
bool vis[23333][23333]; // 记录是否有该点

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d", &x[i], &y[i]);
        vis[x[i]][y[i]] = 1;
    }
    for(int i = 1; i < n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            int s = x[i] + y[i] + x[j] + y[j]; // 求和，化简一下代码
            if(s & 1) continue; // 如果和是奇数，则根据公式，另外两点不在整点，可以直接舍去
            else s >>= 1;
            int x1 = s - y[j], y1 = s - x[i], x2 = s - y[i], y2 = s - x[j]; // 套公式
            if(x1 >= 0 && y1 >= 0 && x2 >= 0 && y2 >= 0 && vis[x1][y1] && vis[x2][y2]) // 记得判边界
                ans = max(ans, (x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i]) >> 1); // 如果有这个点，更新答案为原面积与该面积的最大值
        }
    }
    printf("%d", ans);
    return 0;
}