Cod sursa(job #44787)

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

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

struct segm
{
	double m;
}w[MAX];

int comp(const void *A, const void *B)
{
	if(((segm*)A)->m - ((segm*)B)->m > 0) 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)
			if(v[i].y - v[j].y != 0)
				w[++nsegm].m = (double)(v[i].x - v[j].x)/(v[i].y - v[j].y);
			else w[++nsegm].m = INF;
				
	qsort(w, nsegm+1, sizeof(w[0]), comp);

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