Cod sursa(job #26518)

Utilizator MariusMarius Stroe Marius Data 5 martie 2007 18:10:18
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const char iname[] = "patrate3.in";
const char oname[] = "patrate3.out";

#define MAX_N 1000
#define eps   1e-4
#define abs(z) ((z) < 0 ? (-(z)) : (z))

struct entry {
	double x;
	double y;
} ;

entry P[MAX_N];  int n;


void read_in(void) {
	freopen(iname, "r", stdin);
	int i;
	for (scanf("%d", & n), i = 0; i < n; ++ i)
		scanf("%lf %lf", & P[i].x, & P[i].y);
}

int mycmp(entry z, entry w) {
	if (abs(z.x - w.x) > eps)
		return z.x - w.x <= eps;
	return z.y - w.y <= eps;
}

int search(entry X[], int n, entry p) {
	int k;
	int stp;
	for (stp = 1; stp < n; stp *= 2)
		;
	for (k = 0; stp > 0; stp /= 2)
		if (k + stp < n && mycmp(X[k + stp], p))
			k = k + stp;
	return (abs(p.x - X[k].x) < eps && abs(p.y - X[k].y) < eps);
}

int main(void) {
	read_in();
	sort(P, P + n, mycmp);
	int Res = 0;
	int i;
	int j;
	for (i = 0; i < n - 1; ++ i) {
		for (j = i + 1; j < n; ++ j) {
			entry m, f, g;
			m.x = (P[i].x + P[j].x) / 2.;
			m.y = (P[i].y + P[j].y) / 2.;
			double dx = abs(m.x - P[i].x);
			double dy = abs(m.y - P[i].y);
			if (P[i].y < P[j].y) {
				f.x = m.x + dy, f.y = m.y - dx;
				g.x = m.x - dy, g.y = m.y + dx;
			} else {
				f.x = m.x - dy, f.y = m.y - dx;
				g.x = m.x + dy, g.y = m.y + dx;
			}
			if (search(P, n, f) && search(P, n, g))
				Res ++;
		}
	}
	freopen(oname, "w", stdout);
	printf("%d\n", Res / 2);
	return 0;
}