Cod sursa(job #3145093)

Utilizator daristyleBejan Darius-Ramon daristyle Data 12 august 2023 17:11:37
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

struct Point{
		int x, y;

		friend ifstream& operator>>(ifstream& fin, Point& self){
			fin >> self.x >> self.y;

			return fin;
		}
};

template<typename T>
T gcd(T a, T b){
	if(!b)
		return a;
	return gcd(b, a % b);
}

struct Slope{
		long long numerator, denominator;

		Slope(){}

		Slope(Point A, Point B){
			numerator = (long long) B.y - A.y;
			denominator = (long long) B.x - A.x;

			long long aux = gcd(numerator, denominator);

			numerator /= aux;
			denominator /= aux;
		}

		bool operator==(const Slope& other) const{
			return numerator == other.numerator && denominator == other.denominator;
		}

		void create(Point A, Point B){
			numerator = (long long) B.y - A.y;
			denominator = (long long) B.x - A.x;

			long long aux = gcd(numerator, denominator);

			numerator /= aux;
			denominator /= aux;
		}

		bool operator<(const Slope& other) const{
			if(denominator * other.denominator < 0)
				return numerator * other.denominator > other.numerator * denominator;
			return numerator * other.denominator < other.numerator * denominator;
		}
};

const int N_MAX = 1e3;
const int LINES = (N_MAX - 1) * N_MAX / 2;
Point point[N_MAX];
Slope slope[LINES];

int main(){
	int n;
	fin >> n;
	for(int i = 0; i < n; ++i)
		fin >> point[i];

	int slopes = 0;

	for(int i = 0; i < n; ++i)
		for(int j = i + 1; j < n; ++j)
			slope[slopes++].create(point[i], point[j]);

	sort(slope, slope + slopes);

	int count = 1, trapeze = 0;
	for(int i = 1; i < slopes; ++i)
		if(slope[i] == slope[i - 1])
			++count;
		else{
			trapeze += (count - 1) * count / 2;
			count = 1;
		}

	fout << trapeze << '\n';

	fin.close();
	fout.close();
	return 0;
}