Cod sursa(job #229989)

Utilizator marinMari n marin Data 12 decembrie 2008 13:57:14
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <stdio.h>
#define DIM 1002

typedef long long tip;




struct punct {
	tip x;
	tip y;
};

void cre(punct *v, tip n);
void corect(tip poz, punct *v, tip n);
void sort(punct *v, tip n);

punct P[DIM];
punct D[DIM*DIM];

tip n,k,i,j,nr,total;

punct pct(punct a,punct b) {
	b.x -= a.x;
	b.y -= a.y;
	if (b.y<0) {
		b.y = -b.y;
		b.x = -b.x;
	}
	return b;
}

tip maiMare(tip a, tip b) {
	return D[a].x*D[b].y-D[a].y*D[b].x;
}

int main(){
	FILE *f = fopen("trapez.in", "r");
	fscanf(f,"%lld",&n);
	for (tip i=1;i<=n;i++) {
		fscanf(f, "%lld %lld", &P[i].x, &P[i].y);
	}
	fclose(f);
	
	for (i=1;i<n;i++)
		for (j=i+1;j<=n;j++) {
			k++;
			D[k] = pct(P[i], P[j]);
		}

	sort(D,k);
	k++;
	D[k].x = -1;
	D[k].y = -1;

	nr=1;
	for (i=2;i<=k;i++)
		if (maiMare(i,i-1)==0)
			nr++;
		else {
			total += (nr*(nr-1)/2);
			nr = 1;
		}
		
	FILE *g = fopen("trapez.out","w");
	fprintf(g,"%lld",total);
	fclose(g);
	return 0;
}



void cre(punct *v, tip n){
  tip i,c,p;
  punct aux;
  for (i=2;i<=n;i++) {
    c = i;
    p = i>>1;
    while ((p)&&(maiMare(c,p)>0)) {
      aux = v[c];
      v[c] = v[p];
      v[p] = aux;
      c = p;
      p = p>>1;
    }
  }
}

void corect(tip poz, punct *v, tip n){
  tip p,c;
  punct aux;
  p = poz;
  c = p<<1;
  while (c<=n) {
    if ((c+1<=n) && (maiMare(c+1,c)>0))
      c++;
    if (maiMare(c,p)>0) {
      aux = v[c];
      v[c] = v[p];
      v[p] = aux;
      p = c;
      c = p<<1;
    } else break;
  }

}

void sort(punct *v, tip n) {
  tip i,p,c;
  punct aux;
  cre(v,n);
  for (i=n;i>1;i--) {
    aux = v[1];
    v[1] = v[i];
    v[i] = aux;
    corect(1,v,i-1);
  }
}