Cod sursa(job #8089)

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

#define MAXN 1024

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

int N;
point P[MAXN];

int find(int x, int y)
{
    int st = 1, dr = N, m, r = 1;
    while(st <= dr)
    {
        m = (st+dr) >> 1;
        if(P[m].x < x || (P[m].x == x && P[m].y <= y))
            r = m, st = m+1;
        else
            dr = m-1;
    }
    if(P[r].x == x && P[r].y == y)
        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, 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;
        if(xf1 & 1)
            continue ;
            
        xf1 >>= 1, xf0 = xm-xf1;

        yf1 = ym+x2-x3;
        if(yf1 & 1)
            continue ;
            
        yf1 >>= 1, yf0 = ym-yf1;

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

    return res >> 1;
}

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

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

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

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

    read_and_solve();

    return 0;
}