平面上有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; }