Cod sursa(job #24843)

Utilizator pocaituDavid si Goliat pocaitu Data 3 martie 2007 18:54:24
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.9 kb
#include<stdio.h>
#define nmax 1003
#define nrmax 1000003
#define fin "trapez.in"
#define fout "trapez.out"
int long n,i,j;
struct puncte
 {int long x,y;} punct[nmax];
struct  punctee
 {int long x,y;} pct[3];

void citire();
void afisare(int long);
int long rezolva();
void form_pct();


int main()
{citire();
 afisare(rezolva());
 return 0;
 }


void citire()
{int long i;
 freopen(fin,"r",stdin);
 scanf("%ld",&n);
 for(i=1;i<=n;i++)
  scanf("%ld %ld",&punct[i].x,&punct[i].y);

}


void afisare(int long sol)
{freopen(fout,"w",stdout);
 printf("%ld",sol);

 fclose(stdout);
 }

/*long long ordoneaza(long long x[nrmax],long long y[nrmax],long long n)
{long long i,j,aux,sol=0,nr;
 for(i=1;i<=n;i++)
  for(j=i+1;j<=n;j++)
	if(y[i]*x[j]<y[j]*x[i]);
	 {aux=x[i];
	  x[i]=x[j];
	  x[j]=aux;
	  aux=y[i];
	  y[i]=y[j];
	  y[j]=aux;
	  }
 for(i=1;i<=n;i++)
  {j=i;nr=0;
   while(y[i]*x[i+1]==y[i+1]*x[i])
	 j++;
   nr=j-i+1;
   i=j;
   sol+=nr*(nr-1)/2;
   }
  return sol;

  }*/







int long rezolva()
{int long oriz=0,vert=0,sol=0,x,y,nr,aux;
 struct
   {int long x[nrmax],y[nrmax],n;} cadr[2];
 cadr[0].n=cadr[1].n=0;


 for(i=1;i<=n;i++)
  for(j=i+1;j<=n;j++)
	 {form_pct();
	  x=pct[2].x-pct[1].x;
	  y=pct[2].y-pct[1].y;
	  if(y==0)
		oriz++;
	  else
	   if(x==0)
		 vert++;

	  if(x>0)
		{cadr[0].x[++cadr[0].n]=x;
		 cadr[0].y[cadr[0].n]=y;
		 }
	  else
		{cadr[1].x[++cadr[1].n]=-1*x;
		 cadr[1].y[cadr[1].n]=y;
		 }
	  }

  sol=oriz*(oriz-1)/2+vert*(vert-1)/2;
  //sol+=ordoneaza(cadr[1].x,cadr[1].y,cadr[1].n);
  //sol+ordoneaza(cadr[2].x,cadr[2].y,cadr[2].n);


  for(i=1;i<=cadr[0].n;i++)
  for(j=i+1;j<=cadr[0].n;j++)
	if(cadr[0].y[i]*cadr[0].x[j]<cadr[0].y[j]*cadr[0].x[i]);
	 {aux=cadr[0].x[i];
	  cadr[0].x[i]=cadr[0].x[j];
	  cadr[0].x[j]=aux;
	  aux=cadr[0].y[i];
	  cadr[0].y[i]=cadr[0].y[j];
	  cadr[0].y[j]=aux;
	  }
 for(i=1;i<=cadr[0].n;i++)
  {j=i;nr=0;
   while(cadr[0].y[i]*cadr[0].x[i+1]==cadr[0].y[i+1]*cadr[0].x[i])
	 j++;
   nr=j-i+1;
   i=j;
   sol+=nr*(nr-1)/2;
   }
 for(i=1;i<=cadr[1].n;i++)
  for(j=i+1;j<=cadr[1].n;j++)
	if(cadr[1].y[i]*cadr[1].x[j]<cadr[1].y[j]*cadr[1].x[i]);
	 {aux=cadr[1].x[i];
	  cadr[1].x[i]=cadr[1].x[j];
	  cadr[1].x[j]=aux;
	  aux=cadr[1].y[i];
	  cadr[1].y[i]=cadr[1].y[j];
	  cadr[1].y[j]=aux;
	  }
 for(i=1;i<=cadr[1].n;i++)
  {j=i;nr=0;
   while(cadr[1].y[i]*cadr[1].x[i+1]==cadr[1].y[i+1]*cadr[1].x[i])
	 j++;
   nr=j-i+1;
   i=j;
   sol+=nr*(nr-1)/2;
   }






  return sol;
  }









void form_pct()
  {
  if(punct[i].y<punct[j].x)
	 {pct[1].y=punct[i].y;
	  pct[1].x=punct[i].x;
	  pct[2].y=punct[j].y;
	  pct[2].x=punct[j].x;
	  }
   else
	 {pct[1].y=punct[j].y;
	  pct[1].x=punct[j].x;
	  pct[2].y=punct[i].y;
	  pct[2].x=punct[i].x;
	  }
  }