Cod sursa(job #70477)

Utilizator zobicaMarin Marin zobica Data 6 iulie 2007 00:54:34
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>

using namespace std;

int n;

long m = 0;

struct panta {
	long x, y;
}; 
panta a[499500], p[1000];


void citire() {
	ifstream fin ("trapez.in");
	fin >> n;
	for (int i = 0; i < n ; i++) 
		fin >> p[i].x >> p[i].y;
	fin.close();
}

void fac_sir_drepte() {
	for (int i = 0; i < n - 1 ; i++) 
		for (int j = i + 1; j < n ; j++) {
			a[m].x = p[i].x - p[j].x;
			a[m++].y = p[i].y - p[j].y;
		}  
}

int mai_mic(panta p1, panta p2) {
	if (p1.y == 0)
		return 0;
	if (p2.y == 0)
		return 1;

	if (p1.x * p1.y < 0 && p2.x * p2.y >= 0)
		return 1;
	if (p1.x * p1.y >= 0 && p2.x * p2.y < 0)
		return 0;
	if (p1.x == 0) 
		return (p2.x * p2.y > 0);
	if (p2.x == 0) 
		return (p1.x * p1.y < 0);
	if (p1.y * p2.x < p2.y * p1.x)
		return 1;
	return 0;
}

int egal(panta p1, panta p2) {
	if (p1.y == 0 && p2.y != 0 || p1.y != 0 && p2.y == 0)
		return 0;
	if (p1.x == 0 && p2.x != 0 || p1.x != 0 && p2.x == 0)
		return 0;
	return (p1.y * p2.x == p2.y * p1.x);
}

void qsort(long st, long dr) {
	long i = st, j = dr;
	panta aux = a[i];
	do {
		while (i < j && !mai_mic(a[j], aux)) 
			j--;
		a[i]=a[j];
		while (i<j && !mai_mic(aux, a[i])) 
			i++;
		a[j]=a[i];
	}  while (i != j);
	a[i] = aux;
	if (st < i - 1) 
		qsort(st, i - 1);
	if (i + 1 < dr) 
		qsort(i + 1, dr);
	a[j] = a[i];	
}	

long long numar() {
	long long nr = 0, l = 1;
	for (long i = 0; i < m - 1; i ++)
		if (egal(a[i], a[i + 1]))
			l++;
		else {
			nr += ((l * (l - 1)) >> 1);
			l = 1;
		}
	nr += ((l * (l - 1)) >> 1);
	return nr;
}


void scrie () {
	ofstream fout("trapez.out");
	fout << numar();
	fout.close();
}

int main() {
	citire();
	fac_sir_drepte();
	qsort(0, m-1);
	scrie();
	return 0;
}