Cod sursa(job #68348)

Utilizator sealTudose Vlad seal Data 27 iunie 2007 16:57:32
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define Nm 1001
#define abs(x) ((x)<0?-(x):(x))
int n,sol;
struct point
{
    int x,y;
} P[Nm];

void read()
{
    char S[50];
    int i;

    freopen("patrate3.in","r",stdin);
    scanf("%d\n",&n);
    for(i=0;i<n;++i)
    {
        gets(S);
        P[i].x=atoi(strtok(S,". "))*10000+atoi(strtok(NULL,". "));
        P[i].y=atoi(strtok(NULL,". "))*10000+atoi(strtok(NULL,". "));
    }
}

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

int bs(int x, int y)
{
    int i=0,j=n-1,k;

    while(i<=j)
    {
        k=(i+j)>>1;
        if(P[k].x==x && P[k].y==y)
            return 1;
        if(x<P[k].x || x==P[k].x && y<P[k].y)
            j=k-1;
        else
            i=k+1;
    }
    return 0;
}

void solve()
{
    int i,j,dx,dy;

    qsort(P,n,sizeof(point),cmp);
    for(i=0;i<n;++i)
        for(j=i+1;j<n;++j)
        {
            dx=abs(P[i].x-P[j].x);
            dy=abs(P[i].y-P[j].y);
            if(bs(P[i].x-dy,P[i].y+dx) && bs(P[j].x-dy,P[j].y+dx))
                ++sol;
        }
}

void write()
{
    freopen("patrate3.out","w",stdout);
    printf("%d\n",sol);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}