Cod sursa(job #2654435)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 30 septembrie 2020 21:48:23
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f ( "triang.in" );
ofstream g ( "triang.out" );
const double eps = 1e-5;
struct punct
{
    double x, y;
};
punct v[1502];
int n;
double dist2 ( const punct &A, const punct &B )
{
    double dx = A.x - B.x, dy = A.y - B.y;
    return dx * dx + dy * dy;
}
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 );
    int ey = egal ( A.y, B.y );

    if ( ex == 0 )
        return ey;

    return ex;
}
bool cmp ( const punct &A, const punct &B )
{
    return egal ( A, B ) < 0;
}
bool cautbin ( punct x )
{
    int p = 1, u = n;

    while ( p <= u )
    {
        int m = ( p + u ) / 2;
        int eg = egal ( v[m], x );

        if ( eg == 0 )
            return 1;

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

    return 0;
}
int main()
{
    f >> n;

    for ( int i = 1; i <= n; i++ )
        f >> v[i].x >> v[i].y;

    sort ( v + 1, v + n + 1, cmp );
    punct A, B, M, C, D;
    int ans = 0;

    for ( int i = 1; i < n; i++ )
        for ( int j = i + 1; j <= n; j++ )
        {
            A = v[i];
            B = v[j];
            double AB = dist2 ( A, B );
            M.x = ( A.x + B.x ) / 2;
            M.y = ( A.y + B.y ) / 2;

            if ( egal ( A.x, B.x )==0 )
            {
                double dis = sqrt ( AB * 3 ) / 2;
                C.y = D.y = M.y;
                C.x = M.x + dis;
                D.x = M.x - dis;
            }
            else
            {
              double tg=(B.y-A.y)/(B.x-A.x);
              double dy=sqrt(3*AB/(1+tg*tg))/2;
              double dx=tg*dy;
              C.x=M.x+dx;
              D.x=M.x-dx;
              C.y=M.y-dy;
              D.y=M.y+dy;
            }
            ans+=cautbin(C)+cautbin(D);
        }

    g << ans/3;
    return 0;
}