Cod sursa(job #2646844)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 2 septembrie 2020 10:26:57
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>
#include <algorithm>
#include <math.h>
#define ERR 0.001
using namespace std;
int n;

struct Andrei{
    double x, y;
} v[ 2005 ];

double mod( double ll ){
    if( ll <= 0 )
        return -ll;
    return ll;
}

int cmp( Andrei p1, Andrei p2 ){
    if( p1.x == p2.x )
        return p1.y < p2.y;
    return p1.x < p2.x;
}

int cautbin( double x, double y ){
    int st = 1;
    int dr = n;
    int mij;
    while( st <= dr ){
        mij = ( st + dr ) / 2;
        if( mod( v[ mij ].x - x ) <= ERR && mod( v[ mij ].y - y ) <= ERR )
            return 1;
        if( v[ mij ].x < x )
            st = mij + 1;
        else dr = mij - 1;
    }
    return 0;
}

int main()
{
    int nr = 0;
    ifstream cin( "triang.in" );
    cin >> n;
    for( int i = 1; i <= n; ++i )
        cin >> v[ i ].x >> v[ i ].y;
    cin.close();
    sort( v + 1, v + n + 1, cmp );
    for( int i = 1; i <= n; ++i )
        for( int j = i + 1; j <= n; ++j ){
            double xm, ym, x1, y1, x2, y2;
            double dist, panta;
            Andrei p1, p2;
            p1.x = v[ i ].x;
            p1.y = v[ i ].y;
            p2.x = v[ j ].x;
            p2.y = v[ j ].y;
            xm = ( p1.x + p2.x ) / 2;
            ym = ( p1.y + p2.y ) / 2;
            dist = ( p2.x - p1.x ) * ( p2.x - p1.x ) + ( p2.y - p1.y ) * ( p2.y - p1.y );
            double dist2 = dist;
            if( mod( p2.x - p1.x ) < ERR ){
                y1 = ym;
                y2 = ym;
                x1 = xm + 0.5d * sqrt( 3 * dist );
                x2 = xm - 0.5d * sqrt( 3 * dist );
            } else {
                panta = ( p2.y - p1.y ) / ( p2.x - p1.x );
                x1 = 0.5d * panta * sqrt( 3 * dist2 / ( 1 + panta * panta ) ) + xm;
                y1 = -0.5d * sqrt( 3 * dist2 / ( 1 + panta * panta ) ) + ym;
                x2 = -0.5d * panta * sqrt( 3 * dist2 / ( 1 + panta * panta ) ) + xm;
                y2 = 0.5d * sqrt ( 3 * dist2 / ( 1 + panta * panta ) ) + ym;
            }
            nr += cautbin( x1, y1 );
            nr += cautbin( x2, y2 );
        }
    ofstream cout( "triang.out" );
    cout << nr / 3 << '\n';
    cout.close();
    return 0;
}