Cod sursa(job #6767)

Utilizator danielpDaniel Pasaila danielp Data 20 ianuarie 2007 22:11:18
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <algorithm>
#include <cstdio>	
using namespace std;

#define MAXN 1011
#define ER 1e-5
#define ABS(a) ((a) < 0 ? -(a) : (a))

int equal(double x, double y)
{
	double d = x - y;

	if (d < -ER)
		return -1;
	if (d > ER)
		return 1;
	return 0;
}

struct punct
{
	double x, y;

	bool operator<(const struct punct a) const
	{
		if (equal(x, a.x))
			return equal(x, a.x) < 0 ? 1 : 0;
		return equal(y, a.y) < 0 ? 1 : 0;
	}
};

int N;
punct P[MAXN];

void read()
{
	int i;

	scanf("%d", &N);

	for (i = 0; i < N; i++)
		scanf("%lf %lf", &P[i].x, &P[i].y);
}

int find(double x, double y)
{
	int i, pas;

	for (pas = 1; pas <= N; pas <<= 1);

	for (i = -1; pas; pas >>= 1)
		if (i + pas < N && (equal(P[i + pas].x, x) == -1 || (!equal(P[i + pas].x, x) && equal(P[i + pas].y, y) <= 0)))
			i += pas;
	if (i == -1)
		return 0;

	if (equal(x, P[i].x) || equal(y, P[i].y))
		return 0;

	return 1;
}

int main()
{
	int i, j, rez = 0;
	double mijx, mijy, dx, dy, x0, y0, x1, y1;

	freopen("patrate3.in", "r", stdin);
	freopen("patrate3.out", "w", stdout);

	read();
	sort(P, P + N);

	for (i = 0; i < N; i++)
		if (!find(P[i].x, P[i].y))
			i++, i--;

	for (i = 0; i < N; i++)
		for (j = i + 1; j < N; j++)
		{
			mijx = (P[i].x + P[j].x) / 2;
			mijy = (P[i].y + P[j].y) / 2;
			dx = ABS(mijx - P[i].x);
			dy = ABS(mijy - P[i].y);
			if (P[i].y < P[j].y)
			{
				x0 = mijx + dy, y0 = mijy - dx;
				x1 = mijx - dy, y1 = mijy + dx;
			}
			else
			{
				x0 = mijx - dy, y0 = mijy - dx;
				x1 = mijx + dy, y1 = mijy + dx;
			}

			if (find(x0, y0) && find(x1, y1))
				rez++;
		}

	printf("%d\n", rez / 2);

	return 0;
}