Cod sursa(job #496165)

Utilizator The_DisturbedBungiu Alexandru The_Disturbed Data 27 octombrie 2010 21:52:43
Problema Oite Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct point 
{
	int x;
	short a,b;
	point *y;
};
point *a[1000000],*t;
int b[1000000][4],c,i,l,m,j,o[1025],max,n;
int h(int k)
{
	float c;
	c=(sqrt(5)+1)/2;
	return (int)(m*((k*c)-(int)(k*c)));
}
void insert(int k)
{
	point *p;
	int q;
	q=h(k);
	if(q>max)max=q;
	p=new point;
	p->x=k;
	p->a=i;
	p->b=j;
	p->y=a[q];
	a[q]=p;
}
void search(point *p)
{
	int q;
	bool ok;
	q=h(l-p->x);
	point *u;
	u=a[q];
	while(u)
	{
		if(u->x==l-p->x)
			if((u->a!=p->a)&&(u->a!=p->b)&&(u->b!=p->a)&&(u->b!=p->b))
			{
				int v[4],i,j;
				v[0]=p->a;
				v[1]=p->b;
				v[2]=u->a;
				v[3]=u->b;
				for(i=0;i<3;i++)
					for(j=i+1;j<4;j++)
						if(v[i]>v[j])
						{
							q=v[i];
							v[i]=v[j];
							v[j]=q;
						}
				ok=true;
				for(i=0;i<n;i++) if(b[i][0]==v[0]&&b[i][1]==v[1]&&b[i][2]==v[2]&&b[i][3]==v[3])ok=false;
				if(ok)
				{
					for(i=0;i<4;i++)b[n][i]=v[i];
					n++;
				}
			}
			u=u->y;
	}
}
int main()
{
	freopen("oite.in","r",stdin);
	freopen("oite.out","w",stdout);
	scanf("%d%d",&c,&l);
	for(i=0;i<c;i++)scanf("%d",&o[i]);
	m=c/3;
	for(i=0;i<c-1;i++)
		for(j=i+1;j<c;j++) insert(o[i]+o[j]);
	for(i=0;i<=max;i++)
	{
		t=a[i];
		while(t)
		{
			search(t);
			t=t->y;
		}
	}
	printf("%d\n",n);
}