P3217 [HNOI2011] 数矩形 解

Gmt丶FFF · 2023-10-12 15:30:07 · 题解

可以知道，矩形的对角线长度相等，且中点重合。

那么我们枚举每两点，然后对所有线段以长度为第一关键字，以中点的横坐标为第二关键字，纵坐标为第三关键字排序，对于每一条线段，前后暴力枚举出长度相等且中点相等的另一条条线段，求出面积即可。

由于矩形上的点四点共圆，由于三不共线点确定一圆，在去除相等点的情况下，圆最多有 O(n^3)，现想让四点共圆的点数尽量多，那么对于共圆的四点，最多只有两个点可以继承到下一个四点共圆里，且需消耗两点。可以感性理解发现网格图时取得最大值，那么此时圆的数量为 O(n^2)，所以暴力枚举不会炸。

时间复杂度瓶颈在于排序，复杂度：O(n^2\times \log_2^2(n^2))。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
const int N=1505;
int n,cnt;
struct node
{
    int x,y;
}a[N];
inline bool cmp2(node x,node y)
{
    if(x.x==y.x)return x.y<y.y;
    return x.x<y.x;
}
inline bool cmp3(node x,node y)
{
    if(x.x==y.x&&x.y==y.y)return 1;
    return 0;
}
struct node2
{
    int x,y,len,px,py;
}p[N*N];
inline bool cmp(node2 x,node2 y)
{
    if(x.len==y.len)
    {
        if(x.px==y.px)return x.py<y.py;
        return x.px<y.px;
    }
    return x.len<y.len;
}
inline int P(int x)
{
    return x*x;
}
inline int calc(__int128 x)
{
    __int128 l=0,r=1e18;
    while(l<r)
    {
        __int128 mid=(l+r)>>1;
        if(mid*mid<x)l=mid+1;
        else r=mid;
    }
    return (int)l;
}
signed main()
{
    freopen("num.in","r",stdin);
    freopen("num.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;i=-~i)scanf("%lld%lld",&a[i].x,&a[i].y);
    sort(a+1,a+1+n,cmp2);
    n=unique(a+1,a+1+n,cmp3)-a-1;
    for(int i=1;i<=n;i=-~i)
    {
        for(int j=i+1;j<=n;j=-~j)
        {
            p[++cnt]={i,j,P(a[i].x-a[j].x)+P(a[i].y-a[j].y),a[i].x+a[j].x,a[i].y+a[j].y};
        }
    }
    sort(p+1,p+1+cnt,cmp);
    __int128 ans=0;
    for(int i=1;i<=cnt;i++)
    {
        for(int j=i+1;j<=cnt;j++)
        {
            if(p[i].len==p[j].len&&p[i].px==p[j].px&&p[i].py==p[j].py)
            {
                int num1=P(a[p[i].x].x-a[p[j].x].x)+P(a[p[i].x].y-a[p[j].x].y);
                int num2=P(a[p[i].x].x-a[p[j].y].x)+P(a[p[i].x].y-a[p[j].y].y);
                __int128 num=(__int128)num1*num2;
                ans=max(ans,num);
            }
            else break;
        }
    }
    int res=calc(ans);
    printf("%lld",res); 
    return 0;
}