Cod sursa(job #4274)

Utilizator alex_damianDamian Alexandru alex_damian Data 2 ianuarie 2007 11:38:48
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>

#define FIN "trapez.in"
#define FOUT "trapez.out"

struct rec {
	long x,y;
} a[1000], pp[600000], p[600000];

long n, i, j, k, poz;
long long s;


void sort(long st, long dr) {
	long p1, p2, k, mij = (st+dr) / 2;
	if (st == dr) return;
  sort(st, mij);
  sort(mij+1, dr);
  for (p1 = st, p2 = mij+1, k = st; p1<=mij || p2<=dr; )
    if (p2>dr || (p1<=mij && p[p1].y * p[p2].x < p[p2].y * p[p1].x))
      pp[k++] = p[p1++];
    else pp[k++] = p[p2++];
 	for (k=st; k<=dr; k++) p[k] = pp[k];
}


int main() {
	freopen(FIN, "r", stdin);
  freopen(FOUT, "w", stdout);
  scanf("%ld", &n);
  for (i=1; i<=n; i++) {
     scanf("%ld %ld", &a[i].x, &a[i].y);
  }
	poz = 0;
	for (i=1; i<n; i++)
     for (j=i+1; j<=n; j++) {
        p[++poz].x = a[j].x - a[i].x;
        p[poz].y = a[j].y - a[i].y;
     }
  sort(1,poz);
  i = 1;
  while (i<poz) {
    k = 0;
    while (p[i].x * p[i+1].y == p[i].y * p[i+1].x && i<poz) {
      i++;
      k++;
    }
    //if (k>0) k++;
    s += k * (k+1) / 2;
    i++;
  }
	printf("%lld", s);
  return 0;
}