Cod sursa(job #1447268)

Utilizator allexx2200Atanasiu Alexandru-Marian allexx2200 Data 3 iunie 2015 23:47:26
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <stdio.h>
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>

#define FIN "trapez.in"
#define FOUT "trapez.out"

#define MAX_POINTS 1000

#define ERR 1e-14f
#define INF 1e10

FILE *in, *out;

int N;
std::pair<int,int> points[MAX_POINTS];
double pante[MAX_POINTS / 2 * (MAX_POINTS+1)];
int sol = 0;

double slope(const std::pair<int, int>& a,const std::pair<int, int>& b){
	if(a.first == b.first) return INF;
	return abs( (double)(a.second-b.second) / (double)(a.first-b.first) );
}

int double_cmp(const void * a, const void * b){
	double x = *(double*)a;
	double y = *(double*)b;
	
	if(x == INF && y == INF) return 0;
	if(x == INF) return 1;
	if(y == INF) return -1;
	if(abs(x - y) < ERR) return 0;
	return x - y;
}

void solve(){
	int k=0;
	for(int i=0; i < N-1; i++){
		for(int j=i+1; j < N; j++){
			pante[k++] = slope(points[i], points[j]);
		}
	}

	qsort (pante, k, sizeof(double), double_cmp);

	int l = 1;
    for(int i = 1; i < k; i++){
        if(abs(pante[i]-pante[i-1]) < ERR){
			l++;
        } else {
            sol += 1LL * l * (l - 1) / 2;
            l = 1;
        }
    }
    sol += 1LL * l * (l - 1) / 2;
}

int main(){
	in = fopen(FIN, "rt");
	out = fopen(FOUT, "wt");
	if(!in || !out) return 1;
	
	fscanf(in, "%d", &N);
	
	int x,y;
	for(int i=0; i < N; i++){
		fscanf(in, "%d%d", &x, &y);
		points[i] = std::pair<int,int>(x,y);
	}

	solve();
	fprintf(out, "%d", sol);

	fclose(in);
	fclose(out);
	return 0;
}