Cod sursa(job #617141)

Utilizator andra23Laura Draghici andra23 Data 13 octombrie 2011 23:52:02
Problema Patrate 3 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<fstream>
#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

const int maxn = 1005;
const int r = 666013;
const int m = 10000;
const int t = 200000001;
vector < pair<int,int> > hash[r+5];
pair <long double,long double> points[maxn];
ofstream g("patrate3.out");

void hashInsert(long double x, long double y) {
	int a = (x+m)*m;
	int b = (y+m)*m;
	long long val = (long long) a*t+b;
	val = val%r;
	hash[val].push_back(make_pair(a,b));
}

int hashSearch(long double x, long double y) {
	int a = (x+m)*m;
	int b = (y+m)*m;
	long long val = (long long) a*t+b;
	val = val%r;
	for (int i = 0; i < (int) hash[val].size(); i++) {
		if (hash[val][i].first == a && hash[val][i].second == b) {
			return 1;
		}
	}
	return 0;
}

int main() {
	ifstream f("patrate3.in");
	
	int n;
	f >> n;
	long double x, y;
	for (int i = 1; i <= n; i++) {
		f >> x >> y;
		points[i] = make_pair(x, y);
		hashInsert(x, y);
	}

	int result = 0;
	long double x1, x2, x3, x4, y1, y2, y3, y4, dx, dy;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i != j) {
				x1 = points[i].first;
				y1 = points[i].second;
				
				x2 = points[j].first;
				y2 = points[j].second;
				
				dx = x2 - x1;
				dy = y2 - y1;
				
				x3 = x1 - dy;
				y3 = y1 + dx;

				x4 = x2 - dy;
				y4 = y2 + dx;
				
				int cod1 = hashSearch(x3, y3);
				int cod2 = hashSearch(x4, y4);
				if (cod1 && cod2) {
					result++;
				}
			}
		}
	}

	result = result>>2;
	g << result << '\n';

	return 0;
}