Cod sursa(job #1053807)

Utilizator ioalexno1Alexandru Bunget ioalexno1 Data 12 decembrie 2013 22:59:28
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 2.55 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;
}