Cod sursa(job #1028834)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 14 noiembrie 2013 18:54:54
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int v[801];

int main () {

    FILE *f, *g;
    f = fopen( "nrtri.in", "r" );
    g = fopen( "nrtri.out", "w" );

    int n, start, stop, mijl, p, nr = 0;

    fscanf( f, "%d", &n );

    for( int i = 0 ; i < n ; ++i )
        fscanf( f, "%d", &v[i] );

    sort( v, v + n );

    if( n < 3 )
        fprintf( g, "0\n" );
    else {
        for( int i = 0 ; i < n - 2 ; ++i )
            for( int j = i + 1 ; j < n - 1 ; ++j ) {
                start = j + 1;
                stop = n - 1;
                while( stop - start > 1 ) {
                    mijl = ( stop + start ) / 2;
                    if( v[mijl] > v[i] + v[j] )
                        stop = mijl;
                    else
                        start = mijl;
                }

                if( v[stop] <= v[i] + v[j] )
                    p = stop;
                else if( v[start] <= v[i] + v[j] )
                    p = start;
                else
                    p = j;
                nr += ( p - j );
            }
        fprintf( g, "%d\n", nr );
    }

    fclose( f );
    fclose( g );

    return 0;
}