Cod sursa(job #2469)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 17 decembrie 2006 12:01:27
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
# include <stdio.h>
# include <stdlib.h>

struct {long int x,y;} p[1000+1];
typedef struct NOD {long int dx, dy; int rep; NOD *tata,*fiustg,*fiudrt;};
NOD *radacina;
int n;long int p_infinit;

void citire()
{
FILE *f=fopen("trapez.in","r");
fscanf(f,"%d",&n);
int i;
for (i=1;i<=n;i++)
	fscanf(f,"%ld%ld",&p[i].x,&p[i].y);
fclose(f);
}

void insert_tree(NOD *r,NOD *tata, long int ch_dx, long int ch_dy,int sd)
{
unsigned long long t1,t2;NOD *p;
if (r)
	{
	t1=(unsigned long long)(*r).dy*ch_dx;t2=(unsigned long long)(*r).dx*ch_dy;
	if (t1==t2) (*r).rep++;
	else if (t1<=t2) insert_tree((*r).fiustg,r,ch_dx,ch_dy,1);
	else insert_tree((*r).fiudrt,r,ch_dx,ch_dy,0);
	}
else
	{
	p=(NOD*) malloc (sizeof(NOD));
	(*p).tata=tata;
	if (sd==0) (*tata).fiudrt=p;
	else       (*tata).fiustg=p;
	(*p).fiustg=NULL;(*p).fiudrt=NULL;(*p).rep=1;(*p).dx=ch_dx;(*p).dy=ch_dy;
	}
}

void make_tree()
{
radacina=(NOD*) malloc (sizeof(NOD));
(*radacina).dx=(*radacina).dy=1;(*radacina).rep=0;(*radacina).tata=(*radacina).fiustg=(*radacina).fiudrt=NULL;
int i,j;long int ch_dx,ch_dy;
for (i=1;i<=n;i++)
	for (j=i+1;j<=n;j++)
		{
		ch_dx=p[j].x-p[i].x;
		ch_dy=p[j].y-p[i].y;
		if (ch_dx<0) {ch_dy*=(-1);ch_dx*=(-1);}
		if (ch_dx!=0) insert_tree(radacina,NULL,ch_dx,ch_dy,0);
		else p_infinit++;
		}
}

long int compute_tree(NOD *nod)
{
if (nod==NULL) return 0;
else return (long int)(*nod).rep*((*nod).rep-1)/2+compute_tree((*nod).fiustg)+compute_tree((*nod).fiudrt);
}

void scrie (long int sol) {FILE *g=fopen("trapez.out","w");fprintf(g,"%ld\n",sol);fcloseall();}

int main()
{
citire();
make_tree();
long int sol=compute_tree(radacina);
sol+=p_infinit*(p_infinit-1)/2;
scrie(sol);
return 0;
}