Cod sursa(job #1625247)

Utilizator xtreme77Patrick Sava xtreme77 Data 2 martie 2016 17:48:25
Problema Patrate 3 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.35 kb
/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "set"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"

const char IN [ ] =  "patrate3.in" ;
const char OUT [ ] = "patrate3.out" ;

using namespace std ;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )

ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;

const int MAX = 1e3 + 14 ;

pair < double , double > p [ MAX ] ;

const double PI = 3.1415926535897932384626433832795 ;

const double EPS = 0.0001 ;

int n ;

int bs ( double a , double b )
{
    int st = 1 ;
    int dr = n ;
    while ( st <= dr )
    {
        int mij = ( st + dr ) >> 1 ;
        if ( p [ mij ].first - a > EPS ) {
            dr = mij - 1 ;
        }
        else if ( p [ mij ].first - a < -EPS ) {
            st = mij + 1 ;
        }
        else {
            if ( p [ mij ].second - b < -EPS ) {
                st = mij + 1 ;
            }
            else if ( p [ mij ].second - b > EPS ) {
                dr = mij - 1 ;
            }
            else {
                //cout << a.first << ' ' << a.second << '\n' ;
                return 1 ;
            }
        }
    }
    return 0 ;
}

int main()
{
    cin >> n ;
    FORN ( i , 1 , n )
        cin >> p [ i ].first >> p [ i ].second ;
    sort ( p + 1 , p + n + 1 ) ;
    double angle ;
    double angle2 ;
    double xx1 , yy1 , xx2 , yy2 ;
    double a , b , c , d ;
    int sol = 0 ;
    FORN ( i , 1 , n )
    {
        FORN ( j , i + 1 , n )
        {
            double panta = ( p [ i ].second - p [ j ].second ) / ( p [ i ].first - p [ j ].first ) ;
            //cout << panta << '\n' ;
            angle = PI / 4.0 - atan ( panta ) ;
            xx1 = cos ( angle ) * p [ i ].first - sin ( angle ) * p [ i ].second ;
            yy1 = sin ( angle ) * p [ i ].first + cos ( angle ) * p [ i ].second ;
            xx2 = cos ( angle ) * p [ j ].first - sin ( angle ) * p [ j ].second ;
            yy2 = sin ( angle ) * p [ j ].first + cos ( angle ) * p [ j ].second ;

            angle2 = - angle ;
            //cout << atan ( panta ) << '\n' ;
            //return 0 ;
            ///cout << angle2 << '\n' ;
            a = cos ( angle2 ) * xx1 - sin ( angle2 ) * yy2 ;
            b = sin ( angle2 ) * xx1 + cos ( angle2 ) * yy2 ;

            c = cos ( angle2 ) * xx2 - sin ( angle2 ) * yy1 ;
            d = sin ( angle2 ) * xx2 + cos ( angle2 ) * yy1 ;

            //int aux = bs ( mp ( a , b ) ) ;
            //int aux2 = bs ( mp ( c , d ) ) ;

            if ( bs ( a , b ) and bs ( c , d ) ){
                ++ sol ;
            }

            //cout << cos ( angle ) << '\n' ;
            //cout << sin ( angle ) << '\n' ;
            //return 0 ;

           // cout << a << ' ' << b << '\n' ;
           // cout << c << ' ' << d << '\n' ;

            //cout << endl ;
            //cout << endl ;
            //cout << endl ;
        }
    }
    cout << sol / 2 << '\n' ;
    return 0;
}