Cod sursa(job #2646759)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 1 septembrie 2020 22:56:49
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#define ERR 0.001
using namespace std;
double xm, ym, x1, y1, x2, y2;
double dist, panta;
int n;

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

int 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;
        else if( v[ mij ].x < x )
            st = mij + 1;
        else dr = mij - 1;
    }
    return 0;
}

int main()
{
    int nr = 0;
    FILE *fin = fopen( "triang.in", "r" );
    fscanf( fin, "%d", &n );
    for( int i = 1; i <= n; ++i )
        fscanf( fin, "%lf%lf", &v[ i ].x, &v[ i ].y );
    fclose( fin );
    sort( v + 1, v + n + 1, cmp );
    for( int i = 1; i <= n; ++i )
        for( int j = i + 1; j <= n; ++j ){
            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 );
        }
    FILE *fout = fopen( "triang.out", "w" );
    fprintf( fout, "%d\n", nr / 3 );
    fclose( fout );
    return 0;
}