Cod sursa(job #77149)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 13 august 2007 14:03:05
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

long long n,nr;
typedef struct
{
  long long x, y;
} Punct;
Punct v[1000];

typedef struct
{
  long long x, y;
} Panta;
Panta a[500000];

long long cmmdc(long long a, long long b)
{
  while (a!=b)
  if (a>b) a-=b;
     else  b-=a;
  return a;
}

void citire()
{
  long long i,j,c;

  freopen("trapez.in","r",stdin);
  freopen("trapez.out","w",stdout);
  scanf("%lld",&n);

  for (i=1; i<=n; i++) scanf("%lld %lld",&v[i].x, &v[i].y);

  for (i=1; i<n; i++)
    for (j=i+1; j<=n; j++)
      {
	a[++nr].y=abs(v[j].y-v[i].y);
	a[nr].x=abs(v[j].x-v[i].x);
	if (a[nr].x && a[nr].y)
	while (cmmdc(abs(a[nr].y),abs(a[nr].x))!=1)
	  {
	    c=cmmdc(a[nr].y,a[nr].x);
	    a[nr].x/=c;
	    a[nr].y/=c;
	  }
	if (a[nr].x==0) a[nr].y=-2;
      }
}

int cmp(const void*u, const void*v)
{
  long long int x=*(long long int*)u, y=*(long long int*)v;
  if(a[x].x==a[y].x) return a[x].y-a[y].y;
    else return a[x].x-a[y].x;
}

void buble()
{
  int ok=0, i;
  Panta aux;
  while (!ok)
    {
      ok=1;
      for (i=1; i<nr; i++)
	if (a[i].x>a[i+1].x || (a[i].x==a[i+1].x&& a[i].y>a[i+1].y))
	  {
	    aux=a[i];
	    a[i]=a[i+1];
	    a[i+1]=aux;
	    ok=0;
	  }
    }
}



int main()
{
  long long i, j, contor=0, k, l, m,p, u;
  citire();
  buble();
  for (i=1; i<nr; i++)
    {
      j=i+1;
      while (a[i].x==a[j].x && a[i].y==a[j].y) j++;
      k=j-i-1;
      l=1;
      if (k)
	{ p=1;
	  if (k>2)
	   {
	    for (m=1; m<=k-2; m++) p*=m;
	    l=p*(m+1)*(m+2);
	    p*=2;
	    contor+=(l/p);
	   }
	  else contor++;
	}
    }
  printf("%lld",contor);
  return 0;
}