Cod sursa(job #1433738)

Utilizator Athena99Anghel Anca Athena99 Data 9 mai 2015 18:56:57
Problema Patrate 3 Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <algorithm>
#include <fstream>

using namespace std;

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

const int nmax= 1000;
const double prec= 0.0001;

struct str {
    double x, y;
};

int n, n2;

double v[nmax+1];
str x[nmax+1];

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

double av( double x ) {
    if ( x<0 ) x= -x;
    return x;
}

bool equal( double x, double y ) {
    double diff= av(x-y);
    if ( diff<=prec ) return 1;
    return 0;
}

bool check( double a, double b ) {
    int left= n, right= 0;
    for ( int step= n2; step>0; step/= 2 ) {
        if ( left-step>0 && x[left-step].x>=a-prec ) {
            left-= step;
        }
        if ( right+step<=n && x[right+step].x<=a+prec ) {
            right+= step;
        }
    }

    int ans= left;
    for ( int step= n2; step>0; step/= 2 ) {
        if ( ans+step<=right && x[ans+step].y<=b ) {
            ans+= step;
        }
    }

    if ( equal(x[ans].x, a) && equal(x[ans].y, b) ) return 1;
    return 0;
}

int main(  ) {
    fin>>n;
    for ( n2= 1; 2*n2<=n; n2*= 2 ) ;
    for ( int i= 1; i<=n; ++i ) {
        fin>>x[i].x>>x[i].y;
    }
    sort(x+1, x+n+1, cmp);

    int sol= 0;
    for ( int i= 1; i<=n-1; ++i ) {
        for ( int j= i+1; j<=n; ++j ) {
            double mx, my, p, q;
            mx= (x[i].x+x[j].x)/2, my= (x[i].y+x[j].y)/2;
            p= av(mx-x[i].x), q= av(my-x[i].y);

            double a1, b1, a2, b2;
            if ( x[i].y<x[j].y ) {
                a1= (mx+q), b1= (my-p);
                a2= (mx-q), b2= (my+p);
            } else {
                a1= (mx-q), b1= (my-p);
                a2= (mx+q), b2= (my+p);
            }

            if ( check(a1, b1) && check(a2, b2) ) {
                ++sol;
            }
        }
    }

    fout<<sol/2<<"\n";

    return 0;
}