Cod sursa(job #1060312)

Utilizator felixiPuscasu Felix felixi Data 17 decembrie 2013 21:14:50
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

int v[10000], rasp=0;

ifstream in("nrtri.in");
ofstream out("nrtri.out");

int cautare(int inceput, int sfarsit, int suma){
    int mij=(inceput+sfarsit)/2;
    if(inceput==sfarsit){
        if(v[inceput]>suma)return inceput;
        else return -1;
    }
    else if( inceput == sfarsit-1 ){
        if(v[inceput]>suma)return inceput;
        else if(v[sfarsit]>suma) return sfarsit;
        else return -1;
    }
    else {
        if ( v[mij]<suma ){
            return cautare( mij, sfarsit, suma );
        }
        else return cautare( inceput, mij, suma );
    }
}

int main()
{
    int n, k, sol=0;
    in>>n;
    for(int i=1; i<=n; i++){
        in>>v[i];
    }
    sort(v+1, v+n+1);
    for(int i=1; i<=n-2; i++){
        for(int j=i+1; j<=n-1; j++){
            k= cautare( j+1, n, v[i]+v[j] );
            if(k!=-1)sol+= (n-k+1);
        }
    }
    out<<sol;
    in.close();
    out.close();
    return 0;
}