Cod sursa(job #12372)

Utilizator dominoMircea Pasoi domino Data 3 februarie 2007 17:52:31
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 1024
#define FIN "patrate3.in"
#define FOUT "patrate3.out"
#define EPS 1e-5
#define less(a, b) ((a) < (b)-EPS)
#define abs(x) ((x) < 0 ? -(x) : (x))
#define eq(a, b) (abs((a)-(b)) < EPS)
#define x first
#define y second
#define mp make_pair

typedef pair<double, double> point;

int N, Res;
point P[MAX_N];

bool cmp(point a, point b)
{
    return less(a.x, b.x) || (eq(a.x, b.x) && less(a.y, b.y));
}

int main(void)
{
    int i, j;
    double x1, y1, x2, y2, x3, y3, x4, y4, a, b, mx, my;
    point *p;
    
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d", &N);
    for (i = 0; i < N; i++)
        scanf("%lf %lf", &P[i].x, &P[i].y);

    sort(P, P+N, cmp);
    for (i = 0; i < N; i++)
        for (j = i+1; j < N; j++)
        {
            x1 = P[i].x, y1 = P[i].y, x2 = P[j].x, y2 = P[j].y;
            mx = (x1+x2)*0.5; my = (y1+y2)*0.5;
            a = y1-y2; b = x2-x1; 
            x3 = a*0.5+mx; y3 = b*0.5+my;
            x4 = -a*0.5+mx; y4 = -b*0.5+my;

            p = lower_bound(P, P+N, mp(x3, y3), cmp);
            if (!eq(p->x, x3) || !eq(p->y, y3)) continue;
            p = lower_bound(P, P+N, mp(x4, y4), cmp);
            if (!eq(p->x, x4) || !eq(p->y, y4)) continue;
            Res++;
        }

    printf("%d\n", Res/2);

    return 0;
}