Cod sursa(job #50061)

Utilizator tvladTataranu Vlad tvlad Data 6 aprilie 2007 19:45:45
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#define dbg if(debug)
using namespace std;

const int N = 1000;
const int INF = 2000000000;
const double PREC = 0.000000001;
struct punct { int x,y; };
bool debug = true;
double m[500000];

double tgdr ( punct a, punct b ) {
	if (a.y == b.y) {
		return 0;
	} else
	if (a.x == b.x) {
		return INF;
	} else {
		return ((double) (a.y - b.y)) / (a.x - b.x);
	}
}

bool eg ( double a, double b ) { return (fabs(a-b) < PREC); }

int main() {
	freopen("trapez.in","r",stdin);
	freopen("trapez.out","w",stdout);

	int n;
	scanf("%d",&n);
	punct* a = (punct*) malloc(n*sizeof(punct));
	for (int i = 0; i<n; ++i) {
		scanf("%d %d",&a[i].x,&a[i].y);
	}
	int p = 0;
	int nm = (n*(n-1))/2;
	for (int i = 0, x = n-1; i<n; ++i, --x) {
		for (int j = i+1; j<n; ++j) {
			m[p+j-i-1] = tgdr(a[i],a[j]);
//			printf("%f ",m[p+j-i-1]);
		}
//		printf("\n");
		p += x;
	}
	free(a);
	sort(m,m + nm);
	
//	dbg for (int i = 0; i<nm; ++i) printf("%f ",m[i]);
//	dbg printf("\n");
	
	int nd = 0;
	int* dif = (int*) malloc( nm * sizeof(int) );
	for (int i = 0; i<nm-1; ++i) {
		if (!eg(m[i],m[i+1])) {
			dif[nd++] = i;
//			printf(" != ");
//		} else {
//			printf(" == ");
		}
	}
	dif[nd++] = nm-1;
//	printf("\n");
	
//	dbg for (int i = 0; i<nd; ++i) {
//		printf("%d ",dif[i]);
//	}
//	dbg printf("\n");
	
	int rez = 0, x;
	for (int i = 0; i<nd-1; ++i) {
		x = (dif[i+1] - dif[i]);
		rez += (x*(x-1)) / 2;
	}
	free(dif);
	printf("%d\n",rez);
	return 0;
}