Cod sursa(job #2842025)

Utilizator LuciBBadea Lucian LuciB Data 30 ianuarie 2022 21:58:52
Problema Trapez Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1000;

struct fractie {
	int a, b; // a / b
};

fractie v[NMAX * NMAX];

bool cmp(fractie x, fractie y) {
	long long p1, p2;
	p1 = (long long) x.a * y.b;
	p2 = (long long) x.b * y.a;
	return p1 <= p2;
}

bool isEqual(fractie x, fractie y) {
	long long p1, p2;
	p1 = (long long) x.a * y.b;
	p2 = (long long) x.b * y.a;
	return p1 == p2;
}

int coordX[NMAX], coordY[NMAX];

int main() {
	int n, i, j, pantaInf, trapez, pante, nr;
	FILE *fin, *fout;

	fin = fopen("trapez.in", "r");
	fscanf(fin, "%d", &n);
	for(i = 0; i < n; i++)
		fscanf(fin, "%d%d", &coordX[i], &coordY[i]);
	fclose(fin);
	pantaInf = 0;
	pante = 0;
	for(i = 0; i < n; i++) {
		for(j = i + 1; j < n; j++) {
			if(coordX[i] == coordX[j]) {
				pantaInf++;
			} else {
				v[pante].a = coordY[j] - coordY[i];
				v[pante].b = coordX[j] - coordX[i];
				pante++;
			}
		}
	}
	sort(v, v + pante, cmp);
	//cout << "pantaInf = " << pantaInf << endl;
	trapez = 1LL * pantaInf * (pantaInf - 1) / 2;
	i = 0;
	while(i < pante) {
		nr = 1;
		while(i < pante - 1 && isEqual(v[i], v[i + 1])) {
			nr++;
			i++;
		}
		//cout << "nr = " << nr << endl;
		trapez += 1LL * nr * (nr - 1) / 2;
		i++;
	}

	fout = fopen("trapez.out", "w");
	fprintf(fout, "%d", trapez);
	fclose(fout);

	return 0;
}