Cod sursa(job #7926)

Utilizator wefgefAndrei Grigorean wefgef Data 23 ianuarie 2007 00:04:54
Problema Patrate 3 Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define punct pair<double, double>

#define Nmax 1024
#define pi M_PI
#define eps 1e-4

punct v[Nmax];
int n;

void readdata()
{
	freopen("patrate3.in", "r", stdin);
	freopen("patrate3.out", "w", stdout);
	
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%lf %lf", &v[i].x, &v[i].y);
}

int egal(punct a, punct b)
{
	return fabs(a.x - b.x) <= eps && fabs(a.y - b.y) <= eps;
}

int find(punct p)
{
	int st = 0, dr = n-1, m;
	while (st <= dr)
	{
		m = (st+dr)/2;
		if (egal(p, v[m])) return 1;
		if (v[m] < p) st = m+1;
		else dr = m-1;
	}
	return 0;
}

void solve()
{
	int i, j, rez = 0;
	double X, Y, aux, Cos = cos(pi/2), Sin = sin(pi/2);
	punct p;
	
	sort(v, v+n);
	for (i = 0; i < n; ++i)
	for (j = i+1; j < n; ++j)
	{
		X = (v[i].x+v[j].x)/2;
		Y = (v[i].y+v[j].y)/2;
		aux = X;
		X = X + (v[i].x-X)*Cos - (v[i].y-Y)*Sin;
		Y = Y + (v[i].x-aux)*Sin + (v[i].y-Y)*Cos;
		if (find(mp(X, Y)))
		{
			X = (v[i].x+v[j].x)/2;
			Y = (v[i].y+v[j].y)/2;
			aux = X;
			X = X + (v[j].x-X)*Cos - (v[j].y-Y)*Sin;
			Y = Y + (v[j].x-aux)*Sin + (v[j].y-Y)*Cos;
			if (find(mp(X, Y))) ++rez;		
		}
	}
	printf("%d\n", rez/2);
}

int main()
{
	readdata();
	solve();
	return 0;
}