Cod sursa(job #8067)

Utilizator astronomyAirinei Adrian astronomy Data 23 ianuarie 2007 19:43:25
Problema Patrate 3 Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN 1024
#define eps 0.0001
#define abs(x) ((x) < 0 ? (-(x)) : (x))

typedef struct point { double x, y; } point;

int N;
point P[MAXN];

int find(double x, double y)
{
    int st = 1, dr = N, m, r = 1;
    while(st <= dr)
    {
        m = (st+dr) >> 1;
        if(x-P[m].x > eps || (abs(P[m].x-x) <= eps &&
        (y-P[m].y > eps || abs(y-P[m].y) <= eps)) )
            r = m, st = m+1;
        else
            dr = m-1;
    }
    if(abs(P[r].x-x) <= eps && abs(P[r].y-y) <= eps)
        return 1;
    return 0;
}

int cmp(const void *a, const void *b)
{
    if( ((point*)a)->x == ((point*)b)->x )
        return ((point*)a)->y - ((point*)b)->y;
    return ((point*)a)->x - ((point*)b)->x;
}

int solve(void)
{
    int i, j, res = 0;
    double x2, y2, x3, y3, xm, ym, xf1, xf0, yf1, yf0;

    qsort(P+1, N, sizeof(P[0]), cmp);

    for(i = 1; i <= N; i++)
     for(j = i+1; j <= N; j++)
     {
        x2 = P[j].x, y2 = P[j].y, x3 = P[i].x, y3 = P[i].y;
        xm = x2+x3, ym = y2+y3;

        xf1 = (xm+y3-y2) / 2;
        xf0 = xm-xf1;

        yf1 = (ym+x2-x3) / 2;
        yf0 = ym-yf1;

        if( find(xf1, yf1) && find(xf0, yf0) )
            res++;
     }

    return res >> 1;
}

void read_and_solve(void)
{
    int i;
    double j, k;
    
    scanf("%d\n", &N);

    for(i = 1; i <= N; i++)
    {
        scanf("%lf %lf\n", &j, &k);
        P[i].x = j, P[i].y = k;
    }

    printf("%d\n", solve());
}

int main(void)
{
    freopen("patrate3.in", "rt", stdin);
    freopen("patrate3.out", "wt", stdout);

    read_and_solve();

    return 0;
}