Cod sursa(job #847083)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 3 ianuarie 2013 12:08:20
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
#define eps 1e-5
#define x first
#define y second
using namespace std;
pair < double , double > v [ 1027 ] ;
pair < double , double > temp1, temp2 ;
long n , nr ;
inline bool cmp( pair < double , double > a , pair < double , double > b )
{
    if ( abs ( a . x - b . x ) > eps )
        return a . x < b . x ;
    return a . y < b . y ;
}
inline long cb ( pair < double , double > val , long st , long dr )
{
    long med ;
    while (st <= dr)
    {
        med = ( st + dr ) >> 1 ;
        if ( abs ( val . x - v [ med ] . x ) <= eps && abs ( val . y - v [ med ] . y ) <= eps ) // daca sunt aproximativ egale
            return 1 ; // am gasit solutie
        if ( cmp ( val , v [ med ] ) != 0 )
            dr = med - 1 ;
        else
            st = med + 1 ;
    }
    return 0 ; // nu am gasit solutie
}
int main()
{
    freopen ( "patrate3.in" , "r" , stdin ) ;
    freopen ( "patrate3.out" , "w" , stdout ) ;
    scanf ( "%ld\n" , & n ) ;
    for ( long i = 1; i <= n ; ++ i )
        scanf ( "%lf %lf\n" , & v [ i ] . x , & v [ i ] . y ) ;
    sort ( v + 1, v + n + 1, cmp ) ;
    for ( long i = 1; i <= n ; ++ i )
        for ( long j = i + 1 ; j <= n ; ++ j )
        {
            // coordonate de patrat
            temp1 . x = v [ j ] . x + v [ i ] . y - v [ j ] . y ;
            temp1 . y = v [ j ] . y + v [ j ] . x - v [ i ] . x ;
            temp2 . x = v [ i ] . x + v [ i ] . y - v [ j ] . y ;
            temp2 . y = v [ i ] . y + v [ j ] . x - v [ i ] . x ;
            //verific daca exista nrutiile
            if ( cb ( temp1, 1 , n ) && cb ( temp2 , 1 , n) )
                ++ nr ; // daca le gasesc le pun in nrutie
        }
    nr /= 2 ;
    printf ( "%ld" , nr ) ;
    return 0 ;
}