Cod sursa(job #388602)

Utilizator remusmpRemus MP remusmp Data 30 ianuarie 2010 14:54:01
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
#define INF 2000000000
#define EPS 0.01

int compare(const void* a, const void* b)
{
	double dif = *(double*)a - *(double*)b;
	if (dif > EPS)
		return 1;
	else
		if (dif < EPS)
			return -1;
	return 0;
}

long long int comb2(long long int n)
{
	return (n-1)*n/2;
}

int fcomp(double a, double b)
{
	double dif = a-b;
	if (dif < 0)
		dif = -dif;
	if (dif < EPS)
		return 0;
	return 1;
}
double PANTE[500000];
int main()
{
	FILE* fin = fopen("trapez.in", "r");
	FILE* fout = fopen("trapez.out", "w");

	int N;
	fscanf(fin, "%d", &N);

	int COORD[MAX][2];
	for (int i = 0; i < N; i++)
	{
		fscanf(fin, "%d %d", &COORD[i][0], &COORD[i][1]);
	}

	int ct = 0;
	
	for (int i = 0; i < N-1; i++)
	{
		for (int j = i+1; j < N; j++)
		{
			int dx = COORD[j][0] - COORD[i][0];
			if (dx)
				PANTE[ct++] = (COORD[j][1] - COORD[i][1]) / (double)dx;
			else
				PANTE[ct++] = INF;
		}
	}

	qsort(PANTE, ct, sizeof(double), compare);

	double current = PANTE[0];
	long long int count = 1;
	long long int s = 0;
	for (int i = 1; i < ct; i++)
	{
		if (fcomp(current, PANTE[i])==0)
		{
			count++;
		}
		else
		{
			s += comb2(count);
			count = 1;
			current = PANTE[i];
		}
	}

	fprintf(fout, "%lld", s);

	fclose(fin);
	fclose(fout);

	return 0;
}