Cod sursa(job #2654548)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 1 octombrie 2020 15:51:47
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;
const double EPS = 1e-5,
             R3 = sqrt ( 3.0 );

struct Punct
{
    double x, y;
};

int N;
Punct P[1501];

ofstream g ( "triang.out" );
ifstream f ( "triang.in" );

int egal ( double a, double b )
{
    double d = a - b;

    if ( d < -EPS ) return -1;

    if ( d > +EPS ) return +1;

    return 0;
}

int egal ( const Punct &A, const Punct &B )
{
    int ex = egal ( A.x, B.x ),
        ey = egal ( A.y, B.y );

    if ( ex == 0 ) return ey;

    return ex;
}

bool comp ( const Punct &A, const Punct &B )
{
    return egal ( A, B ) < 0;
}

bool cautbin ( const Punct &A )
{
    int p = 1, u = N;

    while ( p <= u )
    {
        int m = ( p + u ) / 2;
        int e = egal ( P[m], A );

        if ( e == 0 )
            return 1;

        if ( e == 1 )
            u = m - 1;
        else
            p = m + 1;
    }

    return 0;
}

int main()
{
    int i, j, nrTr = 0;
    f >> N;

    for ( i = 1; i <= N; i++ )
        f >> P[i].x >> P[i].y;

    //
    sort ( P + 1, P + N + 1, comp );
    //
    double ddx, ddy;
    Punct M, C, D;

    for ( i = 1; i < N; i++ )
        for ( j = i + 1; j <= N; j++ )
        {
            M.x = ( P[i].x + P[j].x ) / 2;
            M.y = ( P[i].y + P[j].y ) / 2;
            ddx = R3 * ( P[j].y - M.y );
            ddy = R3 * ( P[j].x - M.x );
            C.x = M.x - ddx;
            C.y = M.y + ddy;
            D.x = M.x + ddx;
            D.y = M.y - ddy;
            nrTr += cautbin ( C );
            nrTr += cautbin ( D );
        }

    g << nrTr / 3;
    return 0;
}