平面上有n个关键点,求有多少个四条边都和x轴或者y轴平行的矩形,满足四个顶点都是关键点。给出的关键点可能有重复,但完全重复的矩形只计一次。试补全枚举算法。
#include<iostream>
using namespace std;
struct point{
int x,y,id;
};
bool equals(point a, point b){
return a.x==b.x && a.y == b.y;
}
bool cmp(point a, point b){
return ______(1)_____;
}
void sort(point A[], int n){
for(int i=0;i<n;i++)
for(int j=1;j<n;j++)
if(cmp(A[j],A[j-1])){
point t=A[j];
A[j]=A[j-1];
A[j-1]=t;
}
}
int unique(point A[],int n){
int t=0;
for(int i=0;i<n;i++)
if(_____(2)______)
A[t++]=A[i];
return t;
}
bool binary_search(point A[], int n, int x,int y){
point p;
p.x=x;
p.y=y;
p.id=n;
int a=0, b=n-1;
while(a<b){
int mid=_____(3)______;
if(_____(4)______)
a=mid+1;
else
b=mid;
}
return equals(A[a],p);
}
const int MAXN=1000;
point A[MAXN];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>A[i].x>>A[i].y;
A[i].d=i;
}
sort(A,n);
n=unique(A,n);
int ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(____(5)____ &&binary_search(A,n,A[i].x, A[j].y)
&&binary_search(A,n, A[j].x, A[i].y)){
ans++;
}
cout<<ans<<endl;
return 0;
}