2002.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#define DIFF 20000
#define MAX 1005
#define NUM 40005
#define EP 1e-8
#define LIM 1e-6
#define PI acos(-1.0)
struct pt{
	int x,y;
};
pt p[MAX];
int s[NUM],e[NUM];
int n;
int Max,Min;
bool cmp(pt a,pt b)
{
	return a.x<b.x || a.x==b.x && a.y<b.y;
}

void input()
{
	int i;
	Min=NUM,Max=-1;
	for (i=0;i<n;i++) {
		scanf("%d %d",&p[i].x,&p[i].y);
		p[i].x+=DIFF;
		if (p[i].x<Min) Min=p[i].x;
		if (p[i].x>Max) Max=p[i].x;
	}
	std::sort(p,p+n,cmp);
	for (i=1;i<n;i++)
	memset(s+Min,-1,(Max-Min+2)*sizeof(int));
	s[p[0].x]=0;
	for (i=1;i<n;i++) {
		if (p[i].x!=p[i-1].x) {
			e[p[i-1].x]=i-1;
			s[p[i].x]=i;
		}
	}
	e[p[n-1].x]=n-1;
}

int search(pt z)
{
	if (z.x<Min || z.x>Max || s[z.x]<0) return 0;	
	int a=s[z.x], b=e[z.x], mid,x=z.x,y=z.y;
	while (a<b) {
		mid=(a+b)>>1;
		if (p[mid].y==y) {a=mid; break;}
		else if (p[mid].y<y) a=mid+1;
		else b=mid;
	}
	return (p[a].x==z.x && p[a].y==z.y);
}

void solve()
{
	int i,j;
	double alpha,d;
	double ax,ay,bx,by;
	pt a,b;
	int ans=0;
	for (i=0;i<n;i++) {
		for (j=i+1;j<n;j++) {
			if (p[j].x==p[i].x)	{
				a.x=p[i].x+p[j].y-p[i].y;
				a.y=p[j].y;
				b.x=p[i].x+p[j].y-p[i].y;
				b.y=p[i].y;
				if (search(a) && search(b)) ++ans;
			}
			else if (p[j].y>p[i].y) {

				a.x=p[j].y-p[i].y+p[j].x; a.y=p[i].x-p[j].x+p[j].y;
				if (!search(a)) continue;

				b.x=(p[i].x+a.x)-p[j].x; b.y=(p[i].y+a.y)-p[j].y;
				if (search(b)) ++ans;
			}
		}
	}
	printf("%d\n",ans);
}

int main()
{
	while (scanf("%d",&n)==1) {
		if (!n) break;
		input();
		solve();
	}	
	return 0;
}