本文主要是介绍CodeForces 425D Sereja and Squares，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
平面上有n个点 问 最多能组成多少个边与坐标轴平行的正方形
思路：
这是一个通过不断二分查找乱搞的题…
首先枚举左下角 然后分别往上往右找左上角和右下角
这时如果发现边长不想等就通过长边长度在短边的方向二分查找最接近的值 不停往上往右延伸
如果发现边长想等了 那么要判断一下对应的左上角坐标出是不是有一个点
怎么判断呢 通过将所有点hash出一个值 然后二分…
反正这题就是各种二分乱搞 - -b 复杂度不好算 大概是n*（同x的点数+同y的点数）
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define N 100010
#define LL __int64struct node
{int x,y;
}nd[N];
vector<int> x[N],y[N];
int n,ans;
LL hashnode[N];bool cmpx(node fa,node fb)
{if(fa.x==fb.x) return fa.y<fb.y;return fa.x<fb.x;
}bool cmpy(node fa,node fb)
{if(fa.y==fb.y) return fa.x<fb.x;return fa.y<fb.y;
}int main()
{int i,l,r,u,d,idx,idy,sx,sy,tmp;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d%d",&nd[i].x,&nd[i].y);hashnode[i]=(LL)nd[i].x*200000+nd[i].y;}sort(nd+1,nd+n+1,cmpx);for(i=1;i<=n;i++) x[nd[i].x].push_back(nd[i].y);sort(nd+1,nd+n+1,cmpy);for(i=1;i<=n;i++) y[nd[i].y].push_back(nd[i].x);hashnode[n+1]=(1ULL<<63)-1;sort(hashnode+1,hashnode+n+1);for(i=1;i<=n;i++){d=nd[i].x;l=nd[i].y;idx=lower_bound(x[d].begin(),x[d].end(),l)-x[d].begin()+1;idy=lower_bound(y[l].begin(),y[l].end(),d)-y[l].begin()+1;sx=x[d].size();sy=y[l].size();while(idx<sx&&idy<sy){u=y[l][idy];r=x[d][idx];if(u-d==r-l){tmp=lower_bound(hashnode+1,hashnode+n+2,(LL)u*200000+r)-hashnode;if(hashnode[tmp]==(LL)u*200000+r) ans++;idx++;idy++;}else if(u-d<r-l) idy=lower_bound(y[l].begin(),y[l].end(),d-l+r)-y[l].begin();else if(u-d>r-l) idx=lower_bound(x[d].begin(),x[d].end(),l-d+u)-x[d].begin();}}printf("%d\n",ans);return 0;
}这篇关于CodeForces 425D Sereja and Squares的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
