Cod sursa(job #1312579)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 9 ianuarie 2015 18:49:58
Problema Patrate 3 Scor 15
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.49 kb
#include <stdio.h>
#include <vector>
#include <iostream>
using namespace std;

typedef unsigned int uint;

const int Nmax = 1005;
const int normalize = 10000;
const int hash_size = 611483;
int n;
vector< pair<int, int> > points;
vector< vector< pair<int, int> > > my_hash(hash_size);

inline int get_key(int x) {
	return abs(x % hash_size);
}


void insert_hash(pair<int, int> &p) {
	my_hash[ get_key(p.first) ].push_back(p);
}

bool find_hash(pair<int, int> &p) {
	for (auto point : my_hash[ get_key(p.first) ])
		if (point == p)
			return 1;
	return 0;
}

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

	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		int a, b;
		int x, y;
		pair<int, int> point;

		scanf("%d.%d", &a, &b);
		a *= normalize;
		if (a < 0) x = a - b;
		else x = a + b;

		scanf("%d.%d", &a, &b);
		a *= normalize;
		if (a < 0) y = a - b;
		else y = a + b;

		point = {x, y};
		points.push_back(point); insert_hash(point);
	}

	int result = 0;
	for (uint i = 0; i < points.size(); ++i) {
		int x1 = points[i].first;
		int y1 = points[i].second;
		for (uint j = i + 1; j < points.size(); ++j) {
			int x2 = points[j].first;
			int y2 = points[j].second;
			int ix = x2 - x1;
			int iy = y2 - y1;

			int x3 = iy + x1;
			int y3 = y1 - ix;
			int x4 = iy + x2;
			int y4 = y2 - ix;
			pair<int, int > point1 = {x3, y3},
							point2 = {x4, y4};

			if ( find_hash(point1) && find_hash(point2) )
				++result;
		}
	}

	printf("%d\n", result / 2);

	return 0;
}