Cod sursa(job #6995)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 21 ianuarie 2007 11:31:56
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 9-a si gimnaziu Marime 1.48 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

#define MAXN 1024
#define EPS 0.0001

int N, NR = 0;
vector< pair<double, double> > x;

inline double getdist( pair<double, double> a, pair<double, double> b )
{
	return sqrt( (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second) );
}

int isless( double X1, double Y1, double X2, double Y2 )
{
	if (X2 - X1 >= EPS) return 1;
	if (fabs( X2 - X1 ) < EPS)
	{
		if (Y2 - Y1 >= EPS) return 1;
		if (fabs( Y2 - Y1 ) < EPS) return 1;
		return 0;
	}
	else
		return 0;
}

int find( double X, double Y )
{
	int step = 512, i = 0;
	for (i = 0; step; step >>= 1)
		if (i + step < N && isless(x[i + step].first, x[i + step].second, X, Y))
			i += step;
	if (fabs( x[i].first - X ) > EPS) return 0;
	if (fabs( x[i].second - Y ) > EPS) return 0;
	return 1;
}

int main()
{
	freopen("patrate3.in", "rt", stdin);
	freopen("patrate3.out", "wt", stdout);
	scanf("%d", &N);
	int i, j;
	for (i = 0; i < N; i++)
	{
		double a, b;
		scanf("%lf %lf", &a, &b);
		x.push_back( make_pair(a, b) );
	}
	sort(x.begin(), x.end());

	for (i = 0; i < N; i++)
		for (j = i + 1; j < N; j++)
		{
			double X, Y;

			X = x[i].second - x[j].second + x[i].first;
			Y = x[j].first - x[i].first + x[i].second;
			
			if (!find(X, Y)) continue;

			X = x[i].second - x[j].second + x[j].first;
			Y = x[j].first - x[i].first + x[j].second;

			if (!find(X, Y)) continue;
			NR++;
		}
	printf("%d\n", NR / 2);
	return 0;
}