Cod sursa(job #3263185)

Utilizator AnduRazvanMindrescu Andu AnduRazvan Data 13 decembrie 2024 19:29:12
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n, a[801], z, ct = 0;
///    st1     mij1 st2 mij2      dr1
///5 7 8  9 11 12   12  12   13   14
///i j              z1  z2
int BinarySearch(int st, int dr, int sum)
{
    int z = 0;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(a[mij] <= sum)
        {
            z = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }
    return z;
}
int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> a[i];
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n - 2; i++)
    {
        for(int j = i + 1; j <= n - 1; j++)
        {
            z = BinarySearch(j + 1, n, a[i] + a[j]);
            if(z != 0)
                ct += z - (j + 1) + 1;
        }
    }
    fout << ct;
    return 0;
}