Cod sursa(job #2193637)

Utilizator AndreiVisoiuAndrei Visoiu AndreiVisoiu Data 10 aprilie 2018 20:15:21
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 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);
    //2 3 4 7
    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;
    return 0;
}