【二分查找】-POJ-2002-Squares

本文主要是介绍【二分查找】-POJ-2002-Squares，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://poj.org/problem?id=2002

题目描述：给出平面上若干个点，问能最多构成几个不重复的正方形。

解题思路：

第一反应是标记数组直接搜，好吧，内存超限。然后想了BFS或者DFS，太没前途了。然后想了哈希，不失为一种方法，但是不会操作。好吧还是按照九野大神选题的初衷来做吧——二分查找，为了锻炼自己，嗯！手写！好吧，我写的只是二分找 x 坐标，y 坐标没二分（没想出来。。），直接遍历了，反正也做出来了，而且跑了1000+ms，不错了。后来看了一下 STL 做法，代码也贴上来，以后就用 STL 了。

AC代码：

（看这千疮百孔的注释 _(#`O′) !！！

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;typedef struct node
{int x;int y;
};int num;
node stars[1200];bool cmp(node a,node b)
{if(a.x==b.x)return a.y>b.y;return a.x>b.x;
}int found(node p)
{//cout<<"want: "<<p.x<<" "<<p.y<<endl;int i;/*for(i=0;i<num;i++)if(stars[i].x==p.x&&stars[i].y==p.y)return 1;return 0;*/int l=0,r=num-1,flag=0,fd=-1;while(stars[l].x>=p.x&&stars[r].x<=p.x){//cout<<l<<" "<<r<<endl;if(stars[l].x==p.x){fd=l;break;}if(stars[r].x==p.x){fd=r;break;}if(l+1==r)break;int mid=(l+r)/2;if(stars[l].x>=p.x&&stars[mid].x<=p.x){r=mid;}else{l=mid;}}if(fd!=-1){//cout<<2<<endl;if(stars[fd].y>p.y){while(stars[fd].x==p.x){if(stars[fd].y==p.y){/*cout<<"找到了"<<endl;*/return 1;}fd++;}}else{while(stars[fd].x==p.x){if(stars[fd].y==p.y){/*cout<<"找到了"<<endl;*/return 1;}fd--;}}}return 0;
}int main()
{//freopen("2002_input.txt","r",stdin);//freopen("2002_output.txt","w",stdout);int i,j;while(scanf("%d",&num),num){int ans=0;for(i=0;i<num;i++){scanf("%d%d",&stars[i].x,&stars[i].y);}sort(stars,stars+num,cmp);
/*for(i=0;i<num;i++){cout<<i<<endl;cout<<stars[i].x<<" "<<stars[i].y<<endl;}cout<<endl;
*/node p1,p2;for(i=0;i<num;i++){for(j=i+1;j<num;j++){
/*cout<<"now: "<<endl;cout<<stars[i].x<<" "<<stars[i].y<<endl;cout<<stars[j].x<<" "<<stars[j].y<<endl;
*/p1.x=stars[i].x-(stars[i].y-stars[j].y);p1.y=stars[i].y-(stars[j].x-stars[i].x);p2.x=stars[j].x-(stars[i].y-stars[j].y);p2.y=stars[j].y-(stars[j].x-stars[i].x);
/*cout<<"want: "<<endl;cout<<p1.x<<" "<<p1.y<<endl;cout<<p2.x<<" "<<p2.y<<endl;
*/if(found(p1)&&found(p2))ans++;}}cout<<ans/2<<endl;}return 0;
}

[ STL 版本]

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;typedef struct node
{int x;int y;
};int num;
node stars[1200];bool cmp(node a,node b)
{if(a.x==b.x)return a.y>b.y;return a.x>b.x;
}int main()
{//freopen("2002_input.txt","r",stdin);//freopen("2002_output.txt","w",stdout);int i,j;while(scanf("%d",&num),num){int ans=0;for(i=0;i<num;i++){scanf("%d%d",&stars[i].x,&stars[i].y);}sort(stars,stars+num,cmp);
/*for(i=0;i<num;i++){cout<<i<<endl;cout<<stars[i].x<<" "<<stars[i].y<<endl;}cout<<endl;
*/node p1,p2;for(i=0;i<num;i++){for(j=i+1;j<num;j++){
/*cout<<"now: "<<endl;cout<<stars[i].x<<" "<<stars[i].y<<endl;cout<<stars[j].x<<" "<<stars[j].y<<endl;
*/p1.x=stars[i].x-(stars[i].y-stars[j].y);p1.y=stars[i].y-(stars[j].x-stars[i].x);p2.x=stars[j].x-(stars[i].y-stars[j].y);p2.y=stars[j].y-(stars[j].x-stars[i].x);
/*cout<<"want: "<<endl;cout<<p1.x<<" "<<p1.y<<endl;cout<<p2.x<<" "<<p2.y<<endl;
*/if(binary_search(stars,stars+num,p1,cmp)&&binary_search(stars,stars+num,p2,cmp))ans++;}}cout<<ans/2<<endl;}return 0;
}

AC截图：