Cod sursa(job #2212000)

Utilizator memecoinMeme Coin memecoin Data 12 iunie 2018 19:10:03
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map> 

using namespace std;

pair<int, int> points[1000];

int cmmdc(int a, int b) {
	if (b == 0) {
		return a;
	}
	return cmmdc(b, a % b);
}

int compute(int n) {
	return n * (n - 1) / 2;
}

int main() {
	freopen("trapez.in", "r", stdin);
	freopen("trapez.out", "w", stdout);

	int n;
	scanf("%d", &n);

	map<pair<int, int>, int> nr;

	int x, y;

	for (int i = 0; i < n; ++i) {
		scanf("%d %d", &x, &y);
		points[i] = { x, y };
	}

	int dx, dy, v;

	int vertical = 0;
	int horizontal = 0;

	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			dx = points[i].first - points[j].first;
			dy = points[i].second - points[j].second;

			if (dx == 0) {
				horizontal++;
				continue;
			}
			if (dy == 0) {
				vertical++;
				continue;
			}

			int sign = -1;
			if (dx > 0 && dy > 0) {
				sign = 1;
			}
			if (dx < 0 && dy < 0) {
				sign = 1;
			}

			v = sign * cmmdc(abs(dx), abs(dy));

			pair<int, int> nv = { dx / v, dy / v };

			if (nr.count(nv)) {
				nr[nv]++;
			} else {
				nr[nv] = 1;
			}
		}
	}
	
	int results = compute(horizontal) + compute(vertical);

	for (auto x : nr) {
		results += compute(x.second);
	}

	printf("%d", results);

	return 0;
}