Cod sursa(job #1233459)

Utilizator BonCipBonciocat Ciprian Mircea BonCip Data 25 septembrie 2014 15:07:40
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <stdio.h>

#define N_MAX 800

int v[ N_MAX + 1 ];

void qsort( int beg, int end ) {
    if( end - beg > 1 ) {
        int piv = v[ ( beg * 3 + end * 5 ) / 8 ];
        int l = beg - 1, r = end;
        while( l < r ) {
            while( v[ ++ l ] < piv );
            while( v[ -- r ] > piv );
            if( l < r ) {
                int aux = v[ l ];
                v[ l ] = v[ r ];
                v[ r ] = aux;
            }
        }
        if( l <= ( beg + end ) / 2 ) {
            qsort( beg, l );
            qsort( l, end );
        } else {
            qsort( l, end );
            qsort( beg, l );
        }
    }
}

int main() {
    FILE * fin, * fout;
    fin = fopen( "nrtri.in", "r" );
    fout = fopen( "nrtri.out", "w" );

    int N;
    fscanf( fin, "%d", &N );

    int i, j;
    for( i = 1; i <= N; i ++ ) {
        fscanf( fin, "%d", v + i );
    }

    qsort( 1, N + 1 );

    int cnt = 0;
    for( i = 1; i < N - 1; i ++ ) {
        for( j = i + 1; j < N; j ++ ) {
            int max = j + 1;
            while( v[ i ] + v[ j ] >= v[ max ] && max <= N ) {
                cnt ++;
                max ++;
            }
        }
    }

    for( i = 1; i <= N; i ++ ) {
        printf( "%d ", v[ i ] );
    }

    fprintf( fout, "%d\n", cnt );

    fclose( fin );
    fclose( fout );


    return 0;
}