Cod sursa(job #13112)

Utilizator sims_glAlexandru Simion sims_gl Data 5 februarie 2007 19:27:52
Problema Patrate 3 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

#define nm 1024
#define eps 0.00000001

struct point
{
	double x, y;
};

int n, sol;
point a[nm];

int comp(point a, point b)
{
	return a.x < b.x || (fabs(a.x - b.x) < eps && a.y < b.y);
}

int exista(point t)
{
	int i, crt, step = 1 << 10;

	for (crt = 0; step; step >>= 1)
    	if (crt + step <= n && (a[crt + step].x < t.x || (fabs(a[crt + step].x - t.x) < eps && a[crt + step].y - t.y < eps)))
        	crt += step;

	if (fabs(a[crt].x - t.x) < eps && fabs(a[crt].y - t.y) < eps)
    	return 1;
    else
    	return 0;
}

using namespace std;

int main()
{
	int i, j;
    double dx, dy;
    point tmp1, tmp2;

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

    scanf("%d", &n);

    for (i = 1; i <= n; ++i)
    	scanf("%lf%lf", &a[i].x, &a[i].y);

    sort(a + 1, a + n + 1, comp);

	for (i = 1; i <= n; ++i)
    	for (j = i + 1; j <= n; ++j)
        {
        	dy = a[i].x - a[j].x;
            dx = a[i].y - a[j].y;

            tmp1.x = a[i].x + dx;
            tmp1.y = a[i].y - dy;

            tmp2.x = a[j].x + dx;
            tmp2.y = a[j].y - dy;

            if (exista(tmp1) && exista(tmp2))
            	++sol;

            tmp1.x = a[i].x - dx;
            tmp1.y = a[i].y + dy;

            tmp2.x = a[j].x - dx;
            tmp2.y = a[j].y + dy;

            if (exista(tmp1) && exista(tmp2))
            	++sol;
        }

    printf("%d\n", sol / 4);

	return 0;
}