Cod sursa(job #1059226)

Utilizator ELHoriaHoria Cretescu ELHoria Data 16 decembrie 2013 14:18:19
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.56 kb
#include <complex>
#include <fstream>
#define _USE_MATH_DEFINES
#include <math.h>
#include <limits>
#include <vector>
#include <algorithm>
#define eps 1e-4

using namespace std;

typedef complex<double> Point;
double dot(const Point &a, const Point &b) { return real(conj(a) * b); }
double cross(const Point &a, const Point &b) { return imag(conj(a) * b); }

int comp(const Point &a, const Point &b) {
	if (fabs(real(a) - real(b)) < eps) {
		if (fabs(imag(a) - imag(b)) < eps) {
			return 0;
		}

		return imag(a) < imag(b) ? -1 : 1;
	}
	return real(a) < real(b) ? -1 : 1;
}

bool comp2(const Point &a, const Point &b) {
	return comp(a, b) < 1;
}

int main()
{
	ifstream cin("patrate3.in");
	ofstream cout("patrate3.out");
	vector < Point > v;
	Point origin(0.0, 0.0);
	int n;
	cin >> n;
	v.resize(n); 
	double a, b;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		v[i] = Point(a, b);
	}

	auto bs = [&](Point &p) {
		int ret = 0;
		for (int i = 1 << 10; i > 0; i >>= 1) {
			if (ret + i < n && comp(p, v[ret + i]) > -1) {
				ret += i;
			}
		}
		return comp(p, v[ret]) == 0;
	};
	
	Point p, q;
	int ans = 0;
	sort(v.begin(), v.end(), comp2);
	for (int i = 0; i < n; i++) {
		cout.precision(6);
		for (int j = i + 1; j < n; j++) {
			Point s = v[i] + v[j];
			Point d = v[j] - v[i];
			Point J = Point(-imag(d), real(d));
			p = 0.5 * (s + J);
			q = 0.5 * (s - J);
			if (bs(p) && bs(q)) {
			//	cout << v[i] << " " << v[j] << " " << p << " " << q << "\n";
				ans++;
			}
		}
	}

	cout << ans / 2 << "\n";

	return 0;
}