Cod sursa(job #1447300)

Utilizator allexx2200Atanasiu Alexandru-Marian allexx2200 Data 4 iunie 2015 00:33:35
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb

#include <stdio.h>
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <utility>

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

#define MAX_POINTS 1000

const double ERR = 0.00000000000001;
const int INF = INT_MAX;

FILE *in, *out;

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

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

	if(res == -0) return 0;
	return res;
}

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(fabs(x - y) < ERR) return 0;
	
	if(x - y > 0) return 1;
	return -1;
}

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);
	sort(pante, pante+k);

	for(int i=0; i < k; i++){
		std::cout << pante[i] << " ";
	}
	std::cout << std::endl;
	
	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, "%lli", sol);
	std::cin >> N;
	fclose(in);
	fclose(out);

	return 0;
}


/*
#include <iostream>
#include <fstream>
#include <utility>
#include <algorithm>
 
using namespace std;
 
ifstream fin("trapez.in");
ofstream fout("trapez.out");
 
const int NMax = 1005;
const int INF = 1e9;
const double eror = 1e-14;
 
pair < int, int > v[NMax];
double p[NMax * NMax];
 
inline double get_pant(const pair < int, int > &A, const pair < int, int > &B){
    if(A.first == B.first){
        return INF;
    } else {
        return ((double)(B.second - A.second) / (double)(B.first - A.first));
    }
}
 
inline double mod(double x){
    return max(x, -x);
}
 
int main()
{
    int n, x, y, k, l;
    long long int ans = 0;
    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> x >> y;
        v[i] = make_pair(x, y);
    }
    k = 0;
    for(int i = 1; i < n; i++){
        for(int j = i + 1; j <= n; j++){
            p[++k] = get_pant(v[i], v[j]);
        }
    }
    sort(p + 1, p + k + 1);
    l = 1;

	for(int i=1; i <= k; i++){
		std::cout << p[i] << " ";
	}
	std::cout << std::endl;



    for(int i = 2; i <= k; i++){
        if(mod((p[i - 1] - p[i])) < eror){
            l++;
        } else {
            ans += 1LL * l * (l - 1) / 2;
            l = 1;
        }
    }
    ans += 1LL * l * (l - 1) / 2;
    fout << ans;

		std::cin >> x;
    return 0;
}

*/