Pagini recente » Cod sursa (job #1146157) | Cod sursa (job #300531) | Cod sursa (job #364073) | Cod sursa (job #1962591) | Cod sursa (job #2469)
Cod sursa(job #2469)
# 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;
}