Cod sursa(job #1435639)

Utilizator Athena99Anghel Anca Athena99 Data 13 mai 2015 22:52:50
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.03 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 left= 1, right= n, mid;
    while ( left<=right ) {
        mid= (left+right)/2;
        if ( egal(v[mid].x, x) ) {
            if ( egal(v[mid].y, y) ) return 1;
            if ( v[mid].y<y ) left= mid+1;
            else right= mid-1;
        } else {
            if ( v[mid].x<x ) left= mid+1;
            else right= mid-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;
}