Cod sursa(job #1433690)

Utilizator Athena99Anghel Anca Athena99 Data 9 mai 2015 18:05:48
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <algorithm>
#include <fstream>

using namespace std;

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

const int nmax= 1000;
const int vmax= 10000;

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 check( double x ) {
    int ans= 0;
    for ( int step= n2; step>0; step/= 2 ) {
        if ( ans+step<=n && v[ans+step]<=x ) {
            ans+= step;
        }
    }

    if ( v[ans]==x ) 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;
        v[i]= (double)(x[i].x*vmax)+x[i].y;
    }

    sort(v+1, v+n+1);
    sort(x+1, x+n+1, cmp);

    int sol= 0;
    for ( int i= 1; i<=n; ++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, a, b;
            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);
            }
            a= (double)(a1*vmax)+b1;
            b= (double)(a2*vmax)+b2;

            if ( check(a) && check(b) ) {
                ++sol;
            }
        }
    }

    fout<<sol<<"\n";

    return 0;
}