Cod sursa(job #407931)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 2 martie 2010 18:52:08
Problema Patrate 3 Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.59 kb
#include<stdio.h>
#define infile "patrate3.in"
#define outfile "patrate3.out"
#define nmax 1003
#define modulo 1000003
struct pct
{
	double x,y; //coord
}p[nmax]; //punctele
struct lista
{
	struct pct a;
	int p; //punctul si poz
} l[nmax];
int h[modulo]; //tabela dispersie
int nrl; //nr-ul de elemene din lista
int n; //nr-ul de uncte
int nr; //numarul de patrate

inline int modul(int x)
{
	if(x<0) return -x; return  x;
}

inline double dmodul(double x)
{
	if(x<0) return -x; return  x;
}

inline int f(struct pct a)
{
	return modul(((int)(a.x*10000+0.00001)+(int)(a.y*10000+0.00001) )%modulo );
}

inline int compar(double x, double y)
{
	if(dmodul(x-y) <= 0.00001) return 1; return 0;
}

void push(struct pct a)
{
	int x=f(a);
	nrl++; l[nrl].p=h[x]; l[nrl].a=a; h[x]=nrl;
}

int query(struct pct a)
{
	int x=f(a);
	int i;
	for(i=h[x];i;i=l[i].p)
		if(compar(a.x,l[i].a.x) && compar(a.y,l[i].a.y))
			return 1;
	return 0;
}

struct pct rot_left(struct pct a, struct pct b)
{
	struct pct c,d;
	c.x=b.x-a.x;
	c.y=b.y-a.y;
	d.x=a.x-c.y;
	d.y=a.y+c.x;
	return d;
}

void read()
{
	int i;
	scanf("%d\n",&n);
	for(i=1;i<=n;i++)
		scanf("%lf %lf\n",&p[i].x,&p[i].y);
}

void init()
{
	int i;
	
	for(i=1;i<=n;i++)
		push(p[i]);
}

void solve()
{
	int i,j;
	struct pct a,b;
	
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j)
			{
				a=rot_left(p[i],p[j]);
				b=rot_left(a,p[i]);
				if(query(a) && query(b))
					nr++;
			}
}

void write()
{
	printf("%d\n",nr/4);
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	read();
	init();
	solve();
	write();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}