Cod sursa(job #2215127)

Utilizator DawlauAndrei Blahovici Dawlau Data 21 iunie 2018 06:16:26
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

class InParser {

	private:
		ifstream File;
		static const int buffSZ = (1 << 15);
		int buffPos;
		char buff[buffSZ];

		void _advance() {

			if (++buffPos == buffSZ) {

				File.read(buff, buffSZ);
				buffPos = 0;
			}
		}

	public:
		
		InParser(const char *FileName) {

			File.open(FileName);
			buffPos = buffSZ - 1;
		}

		InParser& operator >>(int &no) {

			int sgn = 1;

			while (!isdigit(buff[buffPos])) {

				if (buff[buffPos] == '-')
					sgn = -1;
				_advance();
			}

			no = 0;
			while (isdigit(buff[buffPos])) {

				no = no * 10 + buff[buffPos] - '0';
				_advance();
			}

			if (buff[buffPos] == '.') {

				_advance();
				while (isdigit(buff[buffPos])) {

					no = no * 10 + buff[buffPos] - '0';
					_advance();
				}
			}
			no *= sgn;

			return *this;
		}
};

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

class Point {

	public:
		int x, y;

		bool operator <(const Point &other)const {

			if (this->x == other.x)
				return this->y < other.y;
			return this->x < other.x;
		}
		
		bool operator ==(const Point &other)const {

			return this->x == other.x && this->y == other.y;
		}
};

inline int abs(int no) {

	if (no < 0)
		no = -no;
	return no;
}

inline bool binSearch(const vector <Point> &Arr, const Point &point) {

	int low = 0, high = (int)Arr.size() - 1, mid;

	while (low <= high) {

		int mid = low + ((high - low) >> 1);

		if (Arr[mid] == point)
			return true;
		else if (Arr[mid] < point)
			low = mid + 1;
		else high = mid - 1;
	}
	return false;
}

inline bool makeSquare(const vector <Point> &Arr, const Point &A, const Point &B) {

	if ((A.x + B.x) % 2 || (A.y + B.y) % 2)
		return false;

	Point midPoint = {(A.x + B.x) / 2,
					  (A.y + B.y) / 2};

	int dx = abs(midPoint.x - A.x);
	int dy = abs(midPoint.y - A.y);

	if(B.y <= A.y)
		return binSearch(Arr, { midPoint.x + dy, midPoint.y + dx }) && binSearch(Arr, { midPoint.x - dy, midPoint.y - dx });
	return binSearch(Arr, { midPoint.x + dy, midPoint.y - dx }) && binSearch(Arr, { midPoint.x - dy, midPoint.y + dx });
}

int main() {

	int N;
	fin >> N;

	vector <Point> Arr;
	Arr.resize(N);

	for (int idx = 0; idx < N; ++idx)
		fin >> Arr[idx].x >> Arr[idx].y;

	sort(Arr.begin(), Arr.end());

	long long cnt = 0;

	for (int low = 0; low < N - 1; ++low)
		for (int high = low + 1; high < N; ++high)
			if (makeSquare(Arr, Arr[low], Arr[high]))  // fix a diagonal
				++cnt;
	fout << cnt / 2;
}