Cod sursa(job #409597)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 3 martie 2010 19:11:41
Problema Patrate 3 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
#define MOD 666013
#define ll long long
#define INT 20000
#define x first
#define y second
typedef pair <int,int> p;
vector <int> hash[MOD];
p a[1005];
double x,y;
int n,i,j,MX,MY,DX,DY,X3,Y3,X4,Y4,rez;
int apr(double x)
{
	if(fabs((int)x+1-x)<0.000001)
		return (int) x+1;
	return x;
}
inline int HASH(p a)
{
	return (1LL*abs(a.x)*19+1LL*abs(a.y)*13)%MOD;
}
bool FIND(int niv,p b)
{
	vector <int> ::iterator it;
	for(it=hash[niv].begin();it!=hash[niv].end();it++)
		if(a[*it].x==b.x&&a[*it].y==b.y)
			break;
	return it!=hash[niv].end();
}
inline bool cmp(const p a,const p b)
{
	return a.x<b.x||a.x==b.x&&a.x<b.x;
}
int main()
{
	freopen("patrate3.in","r",stdin);
	freopen("patrate3.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lf%lf",&x,&y);
		a[i].x=apr(x*INT);
		a[i].y=apr(y*INT);
	}
	sort(a+1,a+n+1,cmp);
	for(i=1;i<=n;i++)
		hash[HASH(p(a[i].x,a[i].y))].push_back(i);
	for(i=1;i<n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			MX=(a[i].x+a[j].x)/2;
			MY=(a[i].y+a[j].y)/2;
			DX=abs(MX-a[i].x);
			DY=abs(MY-a[i].y);
			if(a[i].y<=a[j].y)
			{
				X3=MX-DY;
				Y3=MY+DX;
				X4=MX+DY;
				Y4=MY-DX;
			}
			else
			{
				X3=MX-DY;
				Y3=MY-DX;
				X4=MX+DY;
				Y4=MY+DX;
			}
			if(!FIND(HASH(p(X3,Y3)),p(X3,Y3)))
				continue;
			if(!FIND(HASH(p(X4,Y4)),p(X4,Y4)))
				continue;
			++rez;
		}
	}
	printf("%d\n",rez/2);
	return 0;
}