Cod sursa(job #655080)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 1 ianuarie 2012 01:30:21
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

#define NMax 1005
#define pdd pair <double, double>
#define x first
#define y second
#define Precision 1e-5

using namespace std;

pdd P[NMax];
int N, S;

inline int Compare (pdd A, pdd B)
{
    if (A.x-B.x<-Precision)
    {
        return -1;
    }
    if (A.x-B.x>Precision)
    {
        return 1;
    }
    if (A.y-B.y<-Precision)
    {
        return -1;
    }
    if (A.y-B.y>Precision)
    {
        return 1;
    }
    return 0;
}

inline int Search (pdd X)
{
    int L=1, R=N;
    while (L<=R)
    {
        int Mid=(L+R)/2;
        if (Compare (P[Mid], X)==0)
        {
            return Mid;
        }
        if (Compare (P[Mid], X)==-1)
        {
            L=Mid+1;
        }
        if (Compare (P[Mid], X)==1)
        {
            R=Mid-1;
        }
    }
    return -1;
}

void Solve ()
{
    sort (P+1, P+N+1);
    for (int i=1; i<N; ++i)
    {
        for (int j=i+1; j<=N; ++j)
        {
            pdd P1, P2;
            double DX, DY;
            DX=fabs (P[j].x-P[i].x);
            DY=fabs (P[j].y-P[i].y);
            P1.x=P[j].x+DY;
            P1.y=P[j].y-DX;
            P2.x=P[i].x+DY;
            P2.y=P[i].y-DX;
            if (Search (P1)!=-1 and Search (P2)!=-1)
            {
                ++S;
            }
        }
    }
}

void Read ()
{
    freopen ("patrate3.in", "r", stdin);
    scanf ("%d", &N);
    for (int i=1; i<=N; ++i)
    {
        scanf ("%lf %lf", &P[i].x, &P[i].y);
    }
}

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

int main()
{
    Read ();
    Solve ();
    Print ();
    return 0;
}