pku 3432 数正方形 哈西表.txt

NUAA ACM OJ源码

#include <stdio.h>
#include <iostream>
#include <stdio.h>
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iterator>

//PKU 3432 数正方形 哈西表
using namespace std;
#define PB push_back
#define PO pop_back
#define INFI 9999999
#define NMAX 2050
#define CMAX 10000
typedef struct opnode
{
	int x;
	int y;
}opnode;

typedef struct opans
{
	opnode sq[4];
}opans;

opnode node[NMAX];
vector <opnode> mmap[CMAX+5];
opans ans[NMAX*NMAX];

bool cmp(opnode a,opnode b)
{
	if(a.x==b.x) return a.y<b.y;
	else return a.x<b.x;
}

bool same(opans a,opans b)
{
	if(a.sq[0].x==b.sq[0].x && a.sq[0].y==b.sq[0].y && a.sq[1].x==b.sq[1].x && a.sq[1].y==b.sq[1].y && a.sq[2].x==b.sq[2].x && a.sq[2].y==b.sq[2].y) return true;
	else return false;
}
bool cmp1(opans a,opans b)
{
	if(a.sq[0].x==b.sq[0].x)
	{
		if(a.sq[0].y==b.sq[0].y)
		{
			if(a.sq[1].x==b.sq[1].x)
			{
				if(a.sq[1].y==b.sq[1].y)
				{
					if(a.sq[2].x==b.sq[2].x)
					{
						return a.sq[2].y<b.sq[2].y;
					}
					else  return a.sq[2].x<b.sq[2].x;
				}
				else  return a.sq[1].y<b.sq[1].y;
			}
			else  return a.sq[1].x<b.sq[1].x;
		}
		else  return a.sq[0].y<b.sq[0].y;
	}
	else  return a.sq[0].x<b.sq[0].x;
}
void hash(int num)
{
	int i,qt;
	for(i=1;i<=CMAX;i++) mmap[i].clear();
	for(i=1;i<=num;i++)
	{
		qt=(abs(node[i].x)+abs(node[i].y))%CMAX+1;
		mmap[qt].PB(node[i]);
	}
}

void solve(int num)
{
	int i,j,x1,y1,x2,y2,th,flag,sum,totle;
	opnode q1,q2;
	vector <opnode> :: iterator it;
	hash(num);
	sum=0;
	totle=0;
	for(i=1;i<=num;i++)
	{
		for(j=i+1;j<=num;j++)
		{
			flag=0;
			x1=node[i].x-(node[j].y-node[i].y);
			y1=node[i].y+(node[j].x-node[i].x);
			x2=node[j].x-(node[j].y-node[i].y);
			y2=node[j].y+(node[j].x-node[i].x);
			th=(abs(x1)+abs(y1))%CMAX+1;
			for(it=mmap[th].begin();it!=mmap[th].end();it++)
			{
				if((*it).x==x1 && (*it).y==y1) flag++;
			}
			th=(abs(x2)+abs(y2))%CMAX+1;
			for(it=mmap[th].begin();it!=mmap[th].end();it++)
			{
				if((*it).x==x2 && (*it).y==y2) flag++;
			}
			if(flag==2)
			{
				totle++;
				ans[totle].sq[0].x=x1; ans[totle].sq[0].y=y1;
				ans[totle].sq[1].x=x2; ans[totle].sq[1].y=y2;
				ans[totle].sq[2].x=node[i].x; ans[totle].sq[2].y=node[i].y;
				ans[totle].sq[3].x=node[j].x; ans[totle].sq[3].y=node[j].y;
				sort(ans[totle].sq,ans[totle].sq+4,cmp);
			}

			flag=0;
			x1=node[i].x+(node[j].y-node[i].y);
			y1=node[i].y-(node[j].x-node[i].x);
			x2=node[j].x+(node[j].y-node[i].y);
			y2=node[j].y-(node[j].x-node[i].x);
			th=(abs(x1)+abs(y1))%CMAX+1;
			for(it=mmap[th].begin();it!=mmap[th].end();it++)
			{
				if((*it).x==x1 && (*it).y==y1) flag++;
			}
			th=(abs(x2)+abs(y2))%CMAX+1;
			for(it=mmap[th].begin();it!=mmap[th].end();it++)
			{
				if((*it).x==x2 && (*it).y==y2) flag++;
			}
			if(flag==2)
			{
				totle++;
				ans[totle].sq[0].x=x1; ans[totle].sq[0].y=y1;
				ans[totle].sq[1].x=x2; ans[totle].sq[1].y=y2;
				ans[totle].sq[2].x=node[i].x; ans[totle].sq[2].y=node[i].y;
				ans[totle].sq[3].x=node[j].x; ans[totle].sq[3].y=node[j].y;
				sort(ans[totle].sq,ans[totle].sq+4,cmp);
			}
		}
	}
	if(totle==0) {printf("0\n");return;}
	sum=1;
	sort(ans+1,ans+1+totle,cmp1);
//	printf("totle=%d\n",totle);
	for(i=2;i<=totle;i++)
	{
		if(!same(ans[i-1],ans[i])) sum++;
//		printf("%d %d %d %d %d %d %d %d\n",ans[i].sq[0].x,ans[i].sq[0].y,ans[i].sq[1].x,ans[i].sq[1].y,ans[i].sq[2].x,ans[i].sq[2].y,ans[i].sq[3].x,ans[i].sq[3].y);
	}
	printf("%d\n",sum);
}

int main()
{
	int i,num;
	while(scanf("%d",&num)!=EOF)
	{
		for(i=1;i<=num;i++)
			scanf("%d %d",&node[i].x,&node[i].y);
		solve(num);
	}
	return 0;
}