Cod sursa(job #3124837)

Utilizator daristyleBejan Darius-Ramon daristyle Data 30 aprilie 2023 11:13:08
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <fstream>

using namespace std;

ifstream fin("patrate3.in");
ofstream fout("patrate3.out");

struct Point {
		unsigned int x;
		unsigned int y;

		friend bool operator==(Point &a, Point &b) {
			return a.x == b.x && a.y == b.y;
		}

		friend bool operator!=(Point &a, Point &b) {
			return !(a == b);
		}
};

const int N_MAX = 1e3;
const int MOD_MAX = 9901;
const int VAL_MAX = 1e8;
Point v[N_MAX], A, B, C, D; // AC, BD - diagonals

class HashTable {
private:
		const int NIL = -1;
		int head[MOD_MAX];
		Point key[N_MAX];
		int nxt[N_MAX];
		int mod;
		int curr;

public:
		HashTable(int x) {
			mod = x;

			curr = 0;
			for(int i = 0; i < mod; ++i)
				head[i] = NIL;
			for(int i = 0; i < N_MAX; ++i)
				nxt[i] = NIL;
		}

		const int getkey(Point a) {
			return (a.x ^ a.y) % mod;
		}

		void insert(Point x) {
			int list = getkey(x);
			key[curr] = x;
			nxt[curr] = head[list];
			head[list] = curr;
			++curr;
		}

		bool find(Point x) {
			int list = getkey(x);
			int it = head[list];
			while(it != NIL && key[it] != x)
				it = nxt[it];

			return it != NIL;
		}

		void erase(Point x) {
			int list = getkey(x);
			int ant = head[list], it = nxt[ant];
			if(key[ant] == x){
				head[list] = nxt[ant];
			}else{
				while(it != NIL && key[it] != x){
					ant = it;
					it = nxt[it];
				}

				if(it != NIL){
					nxt[ant] = nxt[it];
				}
			}
		}

};

HashTable ht(MOD_MAX);

int ReadFloatToInt() {
	char ch;
	int num = 0, sgn = 1;

	while(isspace(ch = fin.get()));

	if(ch == '-'){
		sgn = -1;
		ch = fin.get();
	}

	do
		num = num * 10 + ch - '0';
	while(isdigit(ch = fin.get()));
	if(ch == '.')
		while(isdigit(ch = fin.get()))
			num = num * 10 + ch - '0';

	return sgn * num;
}

int main() {
	int n;
	fin >> n;

	for(int i = 0; i < n; ++i){
		v[i].x = ReadFloatToInt() + VAL_MAX;
		v[i].x *= 10;
		v[i].y = ReadFloatToInt() + VAL_MAX;
		v[i].y *= 10;
		ht.insert(v[i]);
	}

	int counter = 0;
	for(int i = 0; i < n - 1; ++i)
		for(int j = i + 1; j < n; ++j){
			A = v[i];
			C = v[j];
			B.x = ((long long) A.x + C.x + C.y - A.y) >> 1;
			B.y = ((long long) A.y + C.y + A.x - C.x) >> 1;
			D.x = ((long long) A.x + C.x - C.y + A.y) >> 1;
			D.y = ((long long) A.y + C.y - A.x + C.x) >> 1;
			if(ht.find(B) && ht.find(D))
				++counter;
		}

	fout << counter / 2 << '\n';

	return 0;
}