Cod sursa(job #17099)

Utilizator alinaddoca alina alinad Data 14 februarie 2007 21:02:56
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<stdio.h>


FILE *f=fopen("trapez.in", "r"), *g=fopen("trapez.out", "w");

int n;
long NR;


struct nod
{
 float info;
 nod *urm;
};

nod *prim, *ultim;



void numarare()
{
 long nr;
 nod *p, *q;
 p=prim;
 NR=0;
 while(p)
  {
   nr=1;
   while(p->info==p->urm->info && p->urm)
    {
     nr++;
     p=p->urm;
    }
   if(nr!=1)
     NR=NR+nr*(nr-1)/2;
   else
     p=p->urm;
  }
}


void insert(float val)
{
 nod *p, *q, *r;

 p=new nod;
 p->urm=NULL;
 p->info=val;

 q=prim;
 while(q && q->info<val)
  {
   r=q;
   q=q->urm;
  }
 if(q==prim)
  if(prim==NULL)
    prim=ultim=p;
  else
    {
     p->urm=prim;
     prim=p;
    }
 else
  if(r==ultim)
   {
    ultim->urm=p;
    ultim=p;
   }
  else
   {
    r->urm=p;
    p->urm=q;
   }
}


int main()
{
 float m;
 int i, j;
 long x[1002], y[1002], nr=0;
 fscanf(f, "%d", &n);
 for(i=1; i<=n; i++)
   fscanf(f, "%ld%ld", &x[i], &y[i]);
 for(i=1; i<n; i++)
  {
   for(j=i+1; j<=n; j++)
    {
     if(x[i]!=x[j] && y[i]!=y[j])
      {
       m=(float)(y[i]-y[j])/(x[i]-x[j]);
       insert(m);
      }
     else
      {
       if(x[i]==x[j])
	{
	 nr++;
	}
       else
	{
	 m=0;
	 insert(m);
	}
      }
    }
  }
 nr=nr*(nr-1)/2;
 numarare();
 NR=NR+nr;
 fprintf(g, "%ld", NR);
 fclose(g);

 return 0;

}