Cod sursa(job #1529486)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 20 noiembrie 2015 22:46:13
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

struct punct{
	int x, y; };

constexpr long long euclid(const long long a, const long long b){
	return (b == 0) ? a : euclid(b, a%b); }

struct panta{
	int dx, dy;
	panta(punct p, punct q): dx(p.x - q.x), dy(p.y - q.y){
		if(dx < 0){
			dx = -dx, dy = -dy; }
		const int gcd = euclid(dx, (dy < 0 ? -dy : dy));
		dx /= gcd, dy /= gcd; }
	bool operator==(const panta& rhs){
		return dx == rhs.dx && dy == rhs.dy; } };

constexpr bool operator<(const panta& a, const panta& b){
	return (a.dx == 0 && b.dx != 0) || (long long)a.dy * (long long)b.dx < (long long)b.dy * (long long)a.dx; }

int main(){
	ifstream f("trapez.in");
	ofstream g("trapez.out");
	int n;
	f >> n;
	vector<punct> pts(n);
	vector<panta> pante;
	for(int i = 0; i < n; ++i){
		f >> pts[i].x >> pts[i].y;
		for(int j = 0; j < i; ++j){
			pante.emplace_back(pts[i], pts[j]); } }

	sort(begin(pante), end(pante));

	long long rez = 0;
	for(auto it = begin(pante), tmp = begin(pante); it != end(pante); it = tmp){
		tmp = find_if_not(it, end(pante), [it](const panta& p){
			return *it == p; });
		const long long nr_paralele = tmp - it;
		rez += (nr_paralele * (nr_paralele-1))/2; }
	g << rez;
	return 0; }