Cod sursa(job #1047858)

Utilizator ioalexno1Alexandru Bunget ioalexno1 Data 4 decembrie 2013 22:30:45
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <fstream>
#include <cmath>

using namespace std;

const int MAX_N = 1010;
double x[MAX_N], y[MAX_N], eps = 0.00001;
int n;

void qsort( int l, int r ){

    int i = l, j = r;
    double mij = x[ ( i + j ) / 2 ];
    do{

        while( x[i] < mij )
            ++i;
        while( x[j] > mij )
            --j;
        if( i <= j ){

            x[i] = x[i] + x[j] - ( x[j] = x[i] );
            y[i] = y[i] + y[j] - ( y[j] = y[i] );
            ++i;
            --j;
            }
    }while( i <= j );
    if( i < r ) qsort( i, r );
    if( l < j ) qsort( l, j );
}

void bubble(){

    bool sorted = false;
    while( !sorted ){

        sorted = true;
        for( int i = 1; i < n; ++i )
            if( x[i] == x[i+1] && y[i] > y[i+1] ){

                y[i] = y[i] + y[i+1] - ( y[i+1] = y[i] );
                sorted = false;
                }
        }
}

double dabs( double x ){

    if( x < 0 ) return -x;
    else return x;
}

bool compare( double z, double q ){

    if( fabs( z - q ) <= eps )
        return 1;
    return 0;
}

bool caut_bin( double x0, double y0 ){

    int l = 1, r = n;
    while( l <= r ){

        int mid = ( l + r ) / 2;
        if( !compare( x[mid], x0 ) ){

            if( x[mid] > x0 ) r = mid - 1;
                    else l = mid + 1;
            }
        else {
            if( !compare( y[mid], y0 ) ){

                if( y[mid] > y0 ) r = mid - 1;
                    else l = mid + 1;
                }
            else return 1;
            }
        }
    return 0;
}

int main()
{
    ifstream cin( "patrate3.in" );
    ofstream cout( "patrate3.out" );

    cin >> n;
    for( int i = 1; i <= n; ++i )
        cin >> x[i] >> y[i];

    qsort( 1, n );
    bubble();
    int res = 0;

    for( int i = 1; i < n; ++i )
        for( int j = i + 1; j <= n; ++j ){

            double mijx = ( x[i] + x[j] ) / 2, mijy = ( y[i] + y[j] ) / 2;
            double dx = fabs( mijx - x[i] ), dy = fabs( mijy - y[i] );
            double x0, y0, x1, y1;
            if( y[i] < y[j] ){

                x0 = mijx + dy;
                y0 = mijy - dx;
                x1 = mijx - dy;
                y1 = mijy + dx;
                }
            else {
                x0 = mijx - dy;
                y0 = mijy - dx;
                x1 = mijx + dy;
                y1 = mijy + dx;
                }
            if( caut_bin( x0, y0 ) && caut_bin( x1, y1) ) ++res;
            }
    cout << res / 2;
    return 0;
}