Cod sursa(job #44674)

Utilizator marinaMarina Horlescu marina Data 31 martie 2007 17:03:54
Problema Trapez Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
//trapez - infoarena
#include <stdio.h>
#include <stdlib.h>
#define INPUT "trapez.in"
#define OUTPUT "trapez.out"
#define MAXN 1001
#define MAX 500501

int N, nsegm = -1;
long long ntrapez;
struct punct
{
	int x,y;
}v[MAXN];

struct segm
{
	long long dx, dy;
}w[MAX];

int comp(const void *A, const void *B)
{
	if( ((segm*)A)->dx * ((segm*)B)->dy > ((segm*)B)->dx * ((segm*)A)->dy) return 1;
	return -1;
}
int main()
{
	freopen(INPUT, "r", stdin);
	scanf("%d", &N);
	int i, j;
	for(i = 1; i <= N; ++i)
		scanf("%d %d", &v[i].x, &v[i].y);
	
	for(i = 1; i < N; ++i)
		for(j = i+1; j <= N; ++j)
			w[++nsegm].dx = v[i].x - v[j].x,
			w[nsegm].dy = v[i].y - v[j].y;
	qsort(w, nsegm, sizeof(w[0]), comp);

	int nr = 0;
	for(i = 2; i <= nsegm; ++i)
	{
		if(w[i-1].dx *w[i].dy == w[i-1].dy * w[i].dx) ++nr;
		else ntrapez += nr * (nr+1)/2, nr = 0;
	}
	ntrapez += nr*(nr+1)/2;
	
	freopen(OUTPUT, "w", stdout);
	printf("%lld\n", ntrapez);
	
	return 0;
}