Cod sursa(job #7918)

Utilizator wefgefAndrei Grigorean wefgef Data 22 ianuarie 2007 23:10:39
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#include <algorithm>
#incldue <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;
		dr = m-1;
	}
	if (egal(p, v[st])) return 1;
	return 0;
}

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

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