数矩形题解

· · 题解

这是一道对本蒟蒻来说比较难的题，经过了好几次改错才做出来，关键其实在于你到底敢不敢打，因为复杂度需要你的勇气。

20 分思路

这也是像我一样的普通选手在测试的时候的思路，我们发现四层枚举 for 循环是会被卡死的，甚至 20 分暴力分数都拿不到。但是大家还记得初中时做过的那种矩形存在性的题吗，其实可以只枚举三个点，另外的一个点其实也就确定了，那么考虑用哈希表存储点的信息，然后就可以用你 n^{3} 的复杂度拿到暴力分数了。

优化思路

其实还是考察数学知识的问题。我们来观察矩形的特点。 矩形具有对角线等长，且对角线互相平分的特点。所以，我们处理出 n ^{2} 条线段，记录每条线段两个端点的信息，以及线段长度和线段中点，对于每两条线段，如果长度相等，中点相等，则更新答案。但我们发现，其实还有诸多问题。

通往正解之路

其实上述思路就是正解，只不过只像优化的思路那样想，还会有问题。

复杂度

我们可以计算这样的复杂度仍然很高，考虑优化。可以对线段的长度先排序，就会得到有序的以长度为关键字排序的线段序列（不保险的话可以以中点坐标为第 2 关键字进行排序，实测没有第二关键字容易被卡常），然后不符合匹配情况时直接跳出就行了。这样能节省不少时间。但还是有问题：万一长度相同的线段有很多条呢？三点可以确定一个圆（不共线），而这样算的话，圆的数量其实最多也就 n^{3}，而要在圆上的点尽量的多，不得不让圆上继承更多公共的点，而每个圆最多能提供两个公共点，也就是说圆的数量不超过 n^{2} 了（有点口糊但是感谢 @Gmt丶FFF 给我讲解的证明，大家可以看他的博客也可以。 这样一来，复杂度的问题就解决了。

如何拒绝精度问题

我在平时打代码的时候十分讨厌这种数学问题带来的精度问题，所以我在不断探索和请教中得出了两个方法。其一是在求中点和线段长度时不必开方或者除以 2 了，直接保留，可以避免精度问题。第二个就是求矩形面积的问题了。在求矩形面积时，我们不可避免要面临精度问题，但我有妙计！上过高中的各位应该都知道由平面向量推导的三角形坐标面积公式：

S=\frac{1}{2}\times \left|x1\times y2+x2\times y3+x3\times y1-x1\times y3-x2\times y1-x3\times y2\right|

那么自然而然矩形的便是：

S=\left|x1\times y2+x2\times y3+x3\times y1-x1\times y3-x2\times y1-x3\times y2\right|

其中三个点的坐标可以随便取。这样一来就完美解决了精度问题。

最后的挣扎

在 debug 过程中，我的最后一步错在了没有 define int long long。我想提醒的是，如果真的脑子糊了想不清楚或者还怕出问题，先放上 define int long long 再说吧。（如果你在卡常当我没说）最后是代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
template< typename T > inline void read(T &x){
    char c=getchar();x=0;int f=0;
    for(;!isdigit(c);c=getchar()) f|=(c=='-');
    for(;isdigit(c);c=getchar()) x=((x<<3)+(x<<1)+(c^48));
    x=f?-x:x;
}
int n;
struct node{
    int ax,ay;
    int bx,by;
    long long d;
    long long cx,cy;
};
node l[2250010];
int tot;
struct Node{
    int x,y;
};
Node wsl[1510];
bool cmp(node a,node b){
    if(a.d==b.d)
    {
        if(a.cx==b.cx)return a.cy>b.cy;
        return a.cx>b.cx;
    }
    return a.d>b.d;
}
long long ans=0;
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        read(wsl[i].x);
        read(wsl[i].y);
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            l[++tot].cx=wsl[i].x+wsl[j].x;
            l[tot].cy=wsl[i].y+wsl[j].y;
            l[tot].ax=wsl[i].x,l[tot].ay=wsl[i].y;
            l[tot].bx=wsl[j].x,l[tot].by=wsl[j].y;
            l[tot].d=1ll*(wsl[i].x-wsl[j].x)*(wsl[i].x-wsl[j].x)+(wsl[i].y-wsl[j].y)*(wsl[i].y-wsl[j].y);
        }
    }//处理每条线段信息 
    sort(l+1,l+1+tot,cmp);
    for(int i=1;i<tot;i++){
        for(int j=i+1;j<=tot;j++){
            if(l[i].d!=l[j].d||l[i].cx!=l[j].cx||l[i].cy!=l[j].cy)break;//不符合直接跳出 
            if(l[i].cx==l[j].cx&&l[i].cy==l[j].cy){
                int wx=l[i].ax,wy=l[i].ay;
                int sx=l[i].bx,sy=l[i].by;
                int lx=l[j].ax,ly=l[j].ay;
                ans=max(ans,1ll*(abs(wx*sy+sx*ly+lx*wy-wy*sx-sy*lx-ly*wx)));//三角形坐标面积公式 
            }
        }
    }
    printf("%lld",ans);
    return 0;
}

在考试以及下来 debug 的过程中有诸多收获，所以分享给诸君了！