问题 4448 --矩形计数(完善程序)

4448: 矩形计数(完善程序)★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 160  解决: 86
[提交][状态][命题人:]

题目描述

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

输入

输出

输出五个选项的答案,大写字母,单独一行,一共五行


提示

来源

 

[提交][状态]