Cod sursa(job #8272)

Utilizator wefgefAndrei Grigorean wefgef Data 24 ianuarie 2007 00:12:29
Problema Patrate 3 Scor 100
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 inline 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 (fabs(p.x - v[m].x) <= eps)
		{
			if (v[m].y < p.y) st = m+1;
			else dr = m-1;
		}
		else
			if (v[m].x < p.x) st = m+1;
			else dr = m-1;
	}
	return 0;
}

void solve()
{
	int i, j, rez = 0;
	double X, Y, aux;
	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].y-Y);
		Y = Y + (v[i].x-aux);
		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].y-Y);
			Y = Y + (v[j].x-aux);
			if (find(mp(X, Y))) ++rez;		
		}
	}
	printf("%d\n", rez/2);
}

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