Cod sursa(job #895484)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 27 februarie 2013 11:34:18
Problema Cautare binara Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include <cstdio>
#include <cmath>
#include <utility>
#include <algorithm>
#define pairdd pair <double, double>
#define eps 0.0000001
#define eps2 0.0001
using namespace std;

int N, nr;
pairdd A[1510];

bool compare(pairdd a, pairdd b) {
	if (a.first < b.first) {
		return true;
	} else if (a.first > b.first) {
		return false;
	} else {
		if (a.second < b.second) {
			return true;
		}
	}
	return false;
}

inline double distanta(pairdd X, pairdd Y) {
	return sqrt( (X.first-Y.first)*(X.first-Y.first) + (X.second-Y.second)*(X.second-Y.second) );
}

bool compara(pairdd x, pairdd y) {
	if (x.first-y.first > eps2) {
		return true;
	} else if ( fabs(x.first-y.first) < eps2 && x.second-y.second>eps2) {
		return true;
	}
	return false;
}

bool cauta(int st, int dr, pairdd aux) {
	int i, logN, lg;
	for (logN = 1; logN <= dr; logN <<= 1);
	
	for (i = N, lg = logN; lg; lg >>= 1) {
		if (i-lg >= st && compara(A[i-lg], aux)) {
			i -= lg;
		}
	}
	if (i == 0) return false;
	if ( fabs(A[i].first-aux.first) < eps2 && (A[i].second-aux.second) < eps2) {
		return true;
	}
	return false;
}

int main() {
	freopen("triang.in", "r", stdin);
	freopen("triang.out", "w", stdout);
	
		scanf("%d", &N);
		
		for (int i = 1; i <= N; ++i) {
			scanf("%lf %lf", &A[i].first, &A[i].second);
		}
		
		sort(A+1, A+N+1, compare);
		
		for (int i = 1; i < N-1; ++i) {
			for (int j = i+1; j < N; ++j) {
				double k = distanta(A[i], A[j]);
				
				pairdd aux;				
				aux.first = A[i].first + (A[j].first - A[i].first)*cos(M_PI/3.) - (A[j].second - A[i].second)*sin(M_PI/3.);
				aux.second = A[i].second + (A[j].first - A[i].first)*sin(M_PI/3.) + (A[j].second - A[i].second)*cos(M_PI/3.);
				if ( cauta(j + 1, N, aux) ) ++nr;

				aux.first = A[i].first + (A[j].first - A[i].first)*cos(-M_PI/3.) - (A[j].second - A[i].second)*sin(-M_PI/3.);
				aux.second = A[i].second + (A[j].first - A[i].first)*sin(-M_PI/3.) + (A[j].second - A[i].second)*cos(-M_PI/3.);
				if ( cauta(j + 1, N, aux) ) ++nr;
			}
		}
		
		printf("%d\n", nr);
	
	return 0;
}