Cod sursa(job #2199394)

Utilizator matei123Biciusca Matei matei123 Data 27 aprilie 2018 15:45:42
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int v[801], n;
int caut(int x, int p)
{   int u = n, poz = -1;
    while(p <= u)
    {   int m = (p+u) / 2;
        if(x >= v[m])
        {   poz = m;
            p = m+1;
        }
        else u = m-1;
    }
    return poz;
}
int main()
{   int p, r = 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; i++)
    {   for(int j = i+1; j <= n; j++)
        {   p = caut(v[i]+v[j], j);
            if(p != -1) r += p-j;
        }
    }
    out << r;
    out.close(); return 0;
}