P3217 [HNOI2011] 数矩形

思路

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

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

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

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

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

时间复杂度为排序的

\mathcal{O}(n^2 \log n)

。

Code

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

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

CPP

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#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;
}

P3217 [HNOI2011] 数矩形

文章操作

思路

Code

相关推荐

评论

P3217 [HNOI2011] 数矩形