Cod sursa(job #1497593)

Utilizator DobosDobos Paul Dobos Data 6 octombrie 2015 23:22:43
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("nrtri.in");
ofstream fout ("nrtri.out");
int v[805],n;
int binar(int li, int ls ,int val)
{
    int mij;
    while(li <= ls){
        mij = (li+ls) / 2;
        if(v[mij] == val)
            return mij;
        else{
            if(v[mij] > val)
                ls = mij - 1;
            else
                li = mij +1;
        }
    }
    return mij;
}
int main()
{
    int n,nr =  0,poz,s;
    fin >> n;
    for(int i = 0; i < n ; i++)
        fin >> v[i];
    sort(v,v+n);
    for(int j = 0; j < n - 2; j++)
    for(int i = j + 1; i < n - 1; i++){
        s = v[j] + v[i];
        poz = binar(i+1,n-1,s);
       // fout << poz << " ";
        while(v[poz] > s && v[poz - 1]  != 0)
            poz--;
        while(v[poz + 1 ] <= s && v[poz + 1] != 0)
            poz++;
        nr += (poz - i);


    }
     fout << nr;
    return 0;
}