4774009_ac_1657ms_288k.cpp

部分PKU上的源码

#include<iostream>
#include<stdlib.h>
using namespace std;
struct point
{
	int x,y;
}q[1005];
int ql;
bool bsearch(point g)
{
	int left=0;
	int right=ql-1;
	while(left<=right)
	{
		int mid=(left+right)/2;
		if(q[mid].x==g.x)
		{
			if(q[mid].y==g.y) return true;
			if(q[mid].y<g.y) left=mid+1;
			else right =mid-1;
		}
		else
			if(q[mid].x<g.x) left=mid+1;
			else right=mid-1;
	}
	return false;
}
int compare(const void *p1,const void *p2)
{
	point q1=*(point *)p1;
	point q2=*(point *)p2;
	if(q1.x!=q2.x) return q1.x-q2.x;
	else return q1.y-q2.y;
}
int main()
{
	while(cin>>ql)
	{
		if(ql==0) return 0;
		int i,j;
		for(i=0;i<ql;i++) {cin>>q[i].x>>q[i].y;q[i].x*=10;q[i].y*=10;}
		qsort(q,ql,sizeof(q[0]),compare);
		int result=0;
		for(i=0;i<ql;i++)
			for(j=i+1;j<ql;j++)
			{
				point mid;
				int lx,ly;
				lx=(q[i].x-q[j].x)/2;
				ly=(q[i].y-q[j].y)/2;
				mid.x=(q[i].x+q[j].x)/2;//由于之前乘以10，所以保证能除尽
				mid.y=(q[i].y+q[j].y)/2;
				point g1,g2;
				g1.x=mid.x+ly;g1.y=mid.y-lx;
				g2.x=mid.x-ly;g2.y=mid.y+lx;
				if(bsearch(g1)&&bsearch(g2)) result++;
			}
		result/=2;
		cout<<result<<endl;
	}
	return 0;
}