Cod sursa(job #2215130)

Utilizator DawlauAndrei Blahovici Dawlau Data 21 iunie 2018 07:50:43
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 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 int nC2(const int &n) {

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

inline double slope(const Point &A, const Point &B) {

	if (A.x == B.x)
		return Inf;
	return 1.0 * (A.y - B.y) / (A.x - B.x);
}

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 < double > slopes;
	slopes.reserve( nC2(N) );

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

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

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

	for (const double &slope : slopes) {
		if (slope == predSlope)
			++cnt;
		else {

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

	fout << ans;
}