Cod sursa(job #1325999)

Utilizator gedicaAlpaca Gedit gedica Data 24 ianuarie 2015 16:30:00
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <algorithm>
#include <fstream>
#include <string>
#include <cstring>

using namespace std;

const int NMAX= 1000, SMAX= 512;

ifstream in( "patrate3.in" );
ofstream out( "patrate3.out" );

struct str
{
    int x, y;
};

inline str mp( const int &x, const int &y )
{
    str sol;
    sol.x = x;
    sol.y = y;
    return sol;
}

bool cmp( const str &x, const str &y )
{
    if ( x.x != y.x )
    {
        return x.x < y.x;
    }
    else
    {
        return x.y < y.y;
    }
}


str v[NMAX+1];

int main(  )
{
    int N;
    in >> N;

    for ( int i= 1; i <= N; ++i )
    {
        string s;
        in >> s;

        for ( int j= 0; j<(int)s.size(); ++j )
        {
            if ( s[j] >= '0' && s[j] <= '9' )
            {
                v[i].x = v[i].x*10+s[j]-'0';
            }
        }

        if ( s[0] == '-' )
        {
            v[i].x *= -1;
        }

        v[i].x *= 2;

        in >> s;

        for ( int j= 0; j < (int)s.size(); ++j )
        {
            if ( s[j] >= '0' && s[j] <= '9' )
            {
                v[i].y = v[i].y*10+s[j]-'0';
            }
        }
        if ( s[0] == '-' )
        {
            v[i].y *= -1;
        }
        v[i].y *= 2;
    }

    sort( v+1, v+N+1, cmp );

    int sol = 0;

    for ( int i= 1; i<N; ++i )
    {
        for ( int j= i+1; j<=N; ++j )
        {
            int c= 0;

            for ( int ind= 0; ind < 2; ++ind )
            {
                str aux;
                int p= 0;

                aux.x = ( v[i].x + v[i].y + v[j].x - v[j].y ) / 2;
                aux.y = ( -v[i].x + v[i].y + v[j].x + v[j].y ) / 2;

                //CB
                for ( int step = SMAX; step > 0; step /= 2 )
                {
                    if ( p+step <= N  && cmp( v[p+step], aux ) )
                    {
                        p+= step;
                    }
                }
                //CB

                if ( p+1 <= N && v[p+1].x == aux.x && v[p+1].y == aux.y )
                {
                    ++c;
                }

                int i_aux= i;
                i= j;
                j= i_aux;

            }
            if ( c== 2 )
            {
                ++sol;
            }
        }
    }

    out << sol/2 << '\n';

    return 0;
}