Cod sursa(job #1054336)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 13 decembrie 2013 18:49:15
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.74 kb
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>

using namespace std;

const double Eps = 0.0001;

#define x first
#define y second

ifstream f("patrate3.in");
ofstream g("patrate3.out");

int n, ans;
vector<pair<double, double> > vec;

bool cmp(const pair<double, double>& a, const pair<double, double>& b) {
	if (abs(a.x - b.x) >= Eps)
		return a.x < b.x;
	return a.y < b.y;
}

bool are_equal(const pair<double, double>& a, const pair<double, double>& b) {
	if (abs(a.x - b.x) < Eps and abs(a.y - b.y) < Eps)
		return true;
	return false;
}

bool caut_bin(const pair<double, double>& p) {

	int st, dr, mij;

	st = 0;
	dr = n - 1;

	while (st <= dr) {
		mij = (st + dr) / 2;
		if (are_equal(p, vec[mij]) == true)
			return true;
		if (cmp(p, vec[mij]))
			dr = mij - 1;
		else
			st = mij + 1;
	}

	return false;
}

int main() {

	int i, j;
	double absc, ordon, centru_x, centru_y, dist_x, dist_y;
	pair<double, double> a, b;

	f >> n;

	vec.resize(n);
	for (i = 0; i < n; ++i) {
		f >> absc >> ordon;
		vec[i] = make_pair(absc, ordon);
	}

	sort(vec.begin(), vec.end());
	for (i = 0; i < n - 1; ++i)
		for (j = i + 1; j < n; ++j) {
			centru_x = (vec[i].x + vec[j].x) / 2;
			centru_y = (vec[i].y + vec[j].y) / 2;
			dist_x = abs(centru_x - vec[i].x);
			dist_y = abs(centru_y - vec[i].y);
			if (vec[i].y < vec[j].y) {
				a = make_pair(centru_x + dist_y, centru_y - dist_x);
				b = make_pair(centru_x - dist_y, centru_y + dist_x);
			} else {
				a = make_pair(centru_x - dist_y, centru_y - dist_x);
				b = make_pair(centru_x + dist_y, centru_y + dist_x);
			}
			if (caut_bin(a) and caut_bin(b))
				ans++;
		}

	g << ans / 2;

	f.close();
	g.close();

	return 0;
}