Cod sursa(job #1426486)

Utilizator Athena99Anghel Anca Athena99 Data 29 aprilie 2015 19:51:53
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.06 kb
#include <algorithm>
#include <cmath>
#include <fstream>

using namespace std;

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

const int nmax= 1500;
const double prec= 0.001;

struct str {
    double x, y;
};

double l[2], k[4];
int n, n2;

str v[nmax+1];

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

bool egal( double a, double b ) {
    double x= (double)a-b;
    if ( x<0 ) x= -x;

    if ( x<prec ) return 1;
    return 0;
}

bool check( double a, double b, double x, double y, double k, double l ) {
    double d0= (double)sqrt((a-x)*(a-x)+(b-y)*(b-y));
    double d1= (double)sqrt((k-x)*(k-x)+(l-y)*(l-y));
    double d2= (double)sqrt((a-k)*(a-k)+(b-l)*(b-l));

    if ( egal(d0, d1) && egal(d0, d2) ) return 1;
    return 0;
}

bool find( double x, double y ) {
    int start= 0, stop= n;
    for ( int step= n2; step>0; step/= 2 ) {
        if ( start+step<=n && v[start+step].x<=(double)x+prec ) {
            start+= step;
        }
        if ( stop-step>0 && v[stop-step].x>=(double)x-prec ) {
            stop-= step;
        }
    }

    for ( int i= start; i<=stop; ++i ) {
        if ( egal(v[i].x, x) && egal(v[i].y, y) ) return 1;
    }
    return 0;
}

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

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

    int sol= 0;
    for ( int i= 1; i<=n-1; ++i ) {
        for ( int j= i+1; j<=n; ++j ) {
            double a, b, x, y, m, d, p, nr, t, raddel;
            a= v[i].x, b= v[i].y, x= v[j].x, y= v[j].y;
            m= ((double)a*a+b*b+x*x-y*y-2*a*x)/2, d= (double)sqrt((a-x)*(a-x)+(b-y)*(b-y));
            p= (double)(a-x)*(a-x)*(d*d-y*y)-m*m, nr= (double)y*(a-x)*(a-x)*2-m*y*2+m*b*2, t= -(double)d*d;
            raddel= (double)sqrt((double)nr*nr-p*t*4);

            l[0]= (double)(-nr-raddel)/((double)t*2);
            l[1]= (double)(-nr+raddel)/((double)t*2);
            k[0]= (double)x+(double)sqrt((double)d*d-y*y+l[0]*y*2-l[0]*l[0]);
            k[1]= (double)x-(double)sqrt((double)d*d-y*y+l[0]*y*2-l[0]*l[0]);
            k[2]= (double)x+(double)sqrt((double)d*d-y*y+l[1]*y*2-l[1]*l[1]);
            k[3]= (double)x-(double)sqrt((double)d*d-y*y+l[1]*y*2-l[1]*l[1]);

            int z= 0;
            str ans[2];
            if ( check(a, b, x, y, k[0], l[0]) ) {
                ans[z].x= k[0], ans[z].y= l[0];
                ++z;
            }
            if ( check(a, b, x, y, k[1], l[0]) ) {
                ans[z].x= k[1], ans[z].y= l[0];
                ++z;
            }
            if ( check(a, b, x, y, k[2], l[1]) ) {
                ans[z].x= k[2], ans[z].y= l[1];
                ++z;
            }
            if ( check(a, b, x, y, k[3], l[1]) ) {
                ans[z].x= k[3], ans[z].y= l[1];
                ++z;
            }

            if ( find(ans[0].x, ans[0].y) ) ++sol;
            if ( find(ans[1].x, ans[1].y) ) ++sol;
        }
    }

    sol/= 3;
    fout<<sol<<"\n";

    return 0;
}