Cod sursa(job #1386120)

Utilizator alexandru70Ungurianu Alexandru alexandru70 Data 12 martie 2015 18:24:32
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct Point {
	double x,y;
};

double slope(Point p1, Point p2) {
	return (p1.y - p2.y)/(p1.x-p2.x);
}

typedef unsigned long long BigUnsigned;

BigUnsigned pair_count(BigUnsigned k) {
	return (k*(k-1))/2;
}

template<typename T>
void print_vector(ostream &os, vector<T> vec) {
	for(const T& val:vec)
		os << val << ' ';
	os << '\n';
}

int main() {

	ifstream in("trapez.in");
	unsigned n;
	in >> n;

	vector<Point> points(n);

	for(Point &point:points) {
		in >> point.x >> point.y;
	}

	in.close();

	vector<double> slopes;
	for(size_t i = 0; i < n; ++i) {
		for(size_t j = i+1; j < n; ++j) {
			slopes.push_back(slope(points[i],points[j]));
		}
	}

	sort(slopes.begin(),slopes.end());

	double currentSlope = slopes[0];
	BigUnsigned count = 1;
	
	BigUnsigned total = 0;

	for(size_t i = 1; i < slopes.size(); ++i) {
		if(currentSlope == slopes[i]) {
			count++;
		}
		else {
			total += pair_count(count);
			currentSlope = slopes[i];
			count = 1;
		}
	}

	ofstream out("trapez.out");

	print_vector(cout,slopes);

	out << total << '\n';

	return 0;
}