Cod sursa(job #8288)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 24 ianuarie 2007 08:33:53
Problema Patrate 3 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

const int N_MAX = 1024;
const long double eps = 0.0001;

int N;

struct pct {
	long double x, y;
} v[N_MAX];

long double mabs(long double a)
{
	return (a < 0 ? -a : a);
}

int cmp(pct a, pct b)
{
	if (mabs(a.x - b.x) < eps) {
		return a.y < b.y;
	}
	return a.x < b.x;
}

int bs(pct A)
{
	int i, step;
	
	for (step = 1; step < N; step <<= 1);
	for (i = 0; step; step >>= 1) {
		if (i + step <= N && ((v[i + step].x < A.x) || (mabs(v[i + step].x - A.x) < eps && v[i + step].y <= A.y + eps))) {
			i += step;
		}
	}

	if (mabs(v[i].x - A.x) <= eps && mabs(v[i].y - A.y) <= eps) {
		return i;
	}
	
	return 0;
}

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

	int i, j, rez1, rez2;
	scanf("%d\n", &N);
	for (i = 1; i <= N; i ++) {
		scanf("%Lf %Lf\n", &v[i].x, &v[i].y);
	}

	sort(v + 1, v + N + 1, cmp);

	pct A, B;
	long double mijx, mijy, dx, dy, x3, y3, x4, y4;
	int nr = 0;
	for (i = 1; i < N; i ++) {
		for (j = i + 1; j <= N; j ++) {
			mijx = (v[i].x + v[j].x) / 2;
			mijy = (v[i].y + v[j].y) / 2;
			dx = mabs(mijx - v[i].x);
			dy = mabs(mijy - v[i].y);

			if (v[i].y < v[j].y) {
				x3 = mijx + dy;
				y3 = mijy - dx;
				x4 = mijx - dy;
				y4 = mijy + dx;

				A.x = x3, A.y = y3, B.x = x4, B.y = y4;
				rez1 = bs(A), rez2 = bs(B);
				if (rez1 && rez2) {
					nr ++;
				}
			} else {
				x3 = mijx - dy;
				y3 = mijy - dx;
				x4 = mijx + dy;
				y4 = mijy + dx;
				
				A.x = x3, A.y = y3, B.x = x4, B.y = y4;
				rez1 = bs(A), rez2 = bs(B);
				if (rez1 && rez2) {
					nr ++;
				}
			}
		}
	}
	printf("%d\n", nr / 2);
	
	return 0;
}