P3217 [HNOI2011] 数矩形

· · 题解

思路

矩形的判定：对角线互相平分且长度相等的四边形为矩形。

若两条线段长度相等且中点重合，则存在一个以这两条线段为对角线的矩形。

枚举每一对点作为线段的两端，存储线段两端坐标、中点坐标以及长度。

将所有线段以长度为第一关键字、中点横坐标为第二关键字、中点纵坐标为第三关键字排序。

对于每一条线段，往前枚举与其长度相等且中点重合的线段并求出对应矩形的面积，更新答案。

:::info[时间复杂度]{open}

排序复杂度为 \mathcal{O}(n^2 \log n)。

枚举矩形的复杂度与矩形个数同阶。

有如下定理：在平面上的 n 个点中任选三个点构成一个三元组 (A,B,C)，线段 AB 与线段 AC 有一夹角。在所有夹角中，任意一个特定的角度出现的次数为 \mathcal{O}(n^2 \log n) ^{\textup{\textmd{\textsf{[1]}}}}。

若三元组 (A,B,C) 满足 AB \perp AC，则称其为「直角三元组」‌。

由上述定理，「直角三元组」‌的个数为 \mathcal{O}(n^2 \log n)。

任意两个矩形不可能有三个相同的顶点，即一个「直角三元组」‌至多对应一个矩形。因此，矩形的个数亦为 \mathcal{O}(n^2 \log n)。

故总复杂度为 \mathcal{O}(n^2 \log n)。

:::

Code

为了避免精度问题，对于中点坐标，可以存储横纵坐标的两倍；对于线段长度，可以存长度的平方。

注意计算矩形面积时会爆 long long，需要使用 __int128 并手写开根。

#include<bits/stdc++.h>
#define int long long
#define lint __int128

const int N=1510; 

using namespace std;

int n,tot,lst,a[N][2],ans;

struct L{
    int x,y,_x,_y,mx,my,len;
    bool operator<(const L &b)const{
        if(len^b.len)return len<b.len;
        if(mx^b.mx)return mx<b.mx;
        return my<b.my;
    }
}c[N*N];

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
    return ret*f;
}

L _init(int x,int y,int _x,int _y){
    int mx=x+_x,my=y+_y,len=(_x-x)*(_x-x)+(_y-y)*(_y-y);
    return (L){x,y,_x,_y,mx,my,len};
}

bool _chk(L c1,L c2){
    return !((c1.mx^c2.mx)||(c1.my^c2.my)||(c1.len^c2.len));
}

int _sqrt(lint x){
    int l=0,r=1e18;
    while(l<=r){
        int mid=(l+r)>>1;
        if((lint)mid*mid==x)return mid;
        if((lint)mid*mid<x)l=mid+1;
        else r=mid-1;
    }
}

lint _calc(int x,int y,int _x,int _y){
    return (lint)(_x-x)*(_x-x)+(lint)(_y-y)*(_y-y);
}

signed main(){
    n=read();
    for(int i=1;i<=n;i++)a[i][0]=read(),a[i][1]=read();
    for(int i=1;i^n;i++)for(int j=i+1;j<=n;j++)c[++tot]=_init(a[i][0],a[i][1],a[j][0],a[j][1]);
    sort(c+1,c+tot+1);
    for(int i=1;i<=tot;i++){
        if(!_chk(c[i],c[lst]))lst=i;
        for(int j=lst;j^i;j++){
            int s=_sqrt(_calc(c[i].x,c[i].y,c[j].x,c[j].y)*_calc(c[i].x,c[i].y,c[j]._x,c[j]._y));
            ans=max(ans,s);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

参考文献

[1] PACH J, SHARIR M. Repeated angles in the plane and related problems[J]. Journal of Combinatorial Theory, Series A, 1992, 59(1): 12-22.