Cod sursa(job #7611)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 21 ianuarie 2007 20:23:14
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

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

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

int N;

int cmp(pct a, pct b)
{
	if (a.x != b.x) {
		return (a.x < b.x);
	} else {
		return (a.y < b.y);
	}
}

int smaller(pct a, pct b)
{
	if (a.x != b.x) {
		if (a.x < b.x) {
			return 1;
		}
		return 0;
	} else {
		if (a.y <= b.y) {
			return 1;
		}
		return 0;
	}
}

int bsearch(pct A)
{
	int i, step;

	for (step = 1; step < N; step <<= 1);
	for (i = 0; step; step >>= 1) {
		if (i + step <= N && smaller(v[i + step], A)) {
			i += step;
		}
	}
	if (v[i].x == A.x && v[i].y == A.y) {
		return i;
	}
	return 0;
}

int mabs(int a)
{
	return (a >= 0 ? a : -a);
}

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

	int x, y;

	int i, j;

	scanf("%d\n", &N);
	for (i = 1; i <= N; i ++) {
		scanf("%d.%d", &x, &y);
		v[i].x = x * 10000 + y;
		scanf(" %d.%d\n", &x, &y);
		v[i].y = x * 10000 + y;
	}
	sort(v + 1, v + N + 1, cmp);

	pct A, B;
	int nr = 0, x3, y3, x4, y4, rez1, rez2;
	for (i = 1; i <= N; i ++) {
		for (j = i + 1; j <= N; j ++) {
			if ((v[i].x <= v[j].x && v[i].y <= v[j].y) || (v[j].x <= v[i].x && v[j].y <= v[i].y)) {
				x3 = v[i].x - mabs(v[i].y - v[j].y);
		   		y3 = v[i].y + mabs(v[i].x - v[j].x);
	
				x4 = v[j].x - mabs(v[i].y - v[j].y);
				y4 = v[j].y + mabs(v[i].x - v[j].x);
	
				A.x = x3, A.y = y3;
				B.x = x4, B.y = y4;
	
				rez1 = bsearch(A), rez2 = bsearch(B);
				if (rez1 && rez2 && rez1 != i && rez1 != j && rez2 != i && rez2 != j) {
					nr ++;
				}
			} else {
				if ((v[j].x <= v[i].x && v[j].y >= v[i].y) || (v[i].x <= v[j].x && v[i].y <= v[j].y)) {
					x3 = v[i].x - mabs(v[i].y - v[j].y);
				   	y3 = v[i].y - mabs(v[i].x - v[j].x);
	
					x4 = v[j].x - mabs(v[i].y - v[j].y);
					y4 = v[j].y - mabs(v[i].x - v[j].x);

					A.x = x3, A.y = y3;
					B.x = x4, B.y = y4;

					rez1 = bsearch(A), rez2 = bsearch(B);
					if (rez1 && rez2 && rez1 != i && rez1 != j && rez2 != i && rez2 != j) {
						nr ++;
					}
				}
			}
		}
	}
	printf("%d\n", nr / 2);

	return 0;
}