Cod sursa(job #7184)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 21 ianuarie 2007 12:59:43
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 9-a si gimnaziu Marime 1.96 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);

	int nr = 0, x3, y3, x4, y4, rez1, rez2;
	for (i = 1; i <= N; i ++) {
		for (j = i + 1; j <= N; j ++) {
			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);

			pct A, B;
			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) {
				printf("%d %d %d %d %d %d\n", i, j, A.x, A.y, B.x, B.y);
				nr ++;
			}

			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) {
				printf("%d %d %d %d %d %d\n", i, j, A.x, A.y, B.x, B.y);
				nr ++;
			}	
		}
	}
	printf("%d\n", nr / 2);

	return 0;
}