Cod sursa(job #2215129)

Utilizator DawlauAndrei Blahovici Dawlau Data 21 iunie 2018 07:38:41
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cfloat>

using namespace std;

ifstream fin("trapez.in");
ofstream fout("trapez.out");

const double Inf = DBL_MAX;
typedef pair <int, int> Pair;

class Point {

	public:
		int x, y;
};

inline long long nC2(const int &n) {

	return 1LL * n * (n - 1) / 2;
}

inline int crossProd(const Pair &a, const Pair &b){

	return a.first * b.second - a.second * b.first;
}

inline bool compCrit(const Pair &a, const Pair &b){

	return crossProd(a, b) < 0;
}

int main() {

	int N;
	fin >> N;

	vector <Point> points;
	points.resize(N);

	for (int idx = 0; idx < N; ++idx)
		fin >> points[idx].x >> points[idx].y;

	vector < Pair > slopes;
	slopes.reserve( nC2(N) );

	for (int low = 0; low < N - 1; ++low)
		for (int high = low + 1; high < N; ++high)
			slopes.emplace_back( points[low].y - points[high].y , points[low].x - points[high].x );

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

	Pair predSlope = *slopes.begin();
	int cnt = 0;
	long long ans = 0;

	for (const Pair &slope : slopes) {
		if (crossProd(slope, predSlope) == 0) 
			++cnt;
		else {

			ans += nC2(cnt);
			cnt = 1;
		}
		predSlope = slope;
	}
	ans += nC2(cnt);

	fout << ans;
}