Cod sursa(job #2304429)

Utilizator florin_salamFlorin Salam florin_salam Data 18 decembrie 2018 00:39:21
Problema Trapez Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <algorithm>

#define mp make_pair

using namespace std;

const int NMAX = 1e3;

struct slope
{
	int dy, dx;
	slope()
	{
		this->dx = this->dy = 0;
	}
	slope(const int &dx, const int &dy)
	{
		this->dx = dx;
		this->dy = dy;
	}
	inline bool operator<(const slope& other) const
	{
		return this->dy * other.dx < this->dx * other.dy;
	}
};

int n;
pair <int, int> v[NMAX + 5];
slope a[NMAX * NMAX + 5];

inline int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

inline bool Check(const slope &x, const slope &y)
{
	//return x.dx == y.dx && x.dy == y.dy;
	return x.dy * y.dx == y.dy * x.dx;
}

int main()
{
	ifstream fin("trapez.in");
	ofstream fout("trapez.out");
	fin >> n;
	int x, y, p = 0;
	for (int i = 1;i <= n;++i)
	{
		fin >> x >> y;
		v[i] = mp(x, y);
	}
	for (int i = 1;i < n;++i)
		for (int j = i + 1;j <= n;++j)
		{
			slope currSlope;
			currSlope.dy = v[j].second - v[i].second;
			currSlope.dx = v[j].first - v[i].first;
			x = gcd(abs(currSlope.dx), abs(currSlope.dy));
			currSlope.dx /= x;
			currSlope.dy /= x;
			a[++p] = currSlope;
		}
	sort(a + 1, a + p + 1);
	long long ans = 0, k = 1;
	for (int i = 2;i <= p + 1;++i)
	{
		if (Check(a[i], a[i - 1]))
			++k;
		else
		{
			ans = 1LL * ans + 1LL * k * (k - 1) / 2;
			k = 1;
		}
	}
	fout << ans << "\n";
	fin.close();
	fout.close();
	return 0;
}