自动搬运

查看原文

来自洛谷，原作者为

	Gmt丶FFF 寄

搬运于2025-08-24 21:46:36，当前版本为作者最后更新于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;
}