Cod sursa(job #1312667)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 9 ianuarie 2015 20:31:05
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
/*
 * Pentru fiecare pereche de puncte (combinari), presupunem ca punctele ar fi
 * puncte opuse (de pe diagonala) si cautam celelalte doua puncte.
 * Pentru a obtine coordonatele celorlalte puncte procedam in felul urmator:
 * Fie m centrul patratului, A si B punctele noastre si C si D punctele pe care
 * vrem sa le gasim. Patratul este ACBD.
 * Vectorul MC este egal cu vectorul MA rotit cu 90 de grade counterclockwise.
 * Asemanator, MD este egal cu MA rotit cu 90 de grade clockwise.
 * Stiind vectorul si coordonata unui punct il putem afla pe celalalt.
 */
#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 get_number(char *s) {
	int number = 0;
	int sign = 1;

	if (*s == '-')
		sign = -1, ++s;

	for (; *s != '\0'; ++s)
		if(*s != '.')
			number = number * 10 + *s - '0';

	return number * sign;
}

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

	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		int x, y;
		pair<int, int> point;
		char buffer[20];

		scanf("%s", buffer);
		x = get_number(buffer);

		scanf("%s", buffer);
		y = get_number(buffer);

		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 mx = (x1 + x2) / 2;
			int my = (y1 + y2) / 2;

			int x3 = mx - (y1 - my);
			int y3 = my + (x1 - mx);
			int x4 = mx + (y1 - my);
			int y4 = my - (x1 - mx);

			pair<int, int> point1 = {x3, y3},
							point2 = {x4, y4};

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

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

	return 0;
}