Cod sursa(job #1971899)

Utilizator gruhtenZinnenberg Gruhten gruhten Data 21 aprilie 2017 11:20:49
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <iostream>
#include <algorithm>
#include <fstream>

using namespace std;

int n, i, j, v[800], st, dr, mid, poz, k;
long nrt;

int main () {

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

    fin >> n;
    for (i = 1; i <= n; i++)    fin >> v[i];
    sort (v+1 , v+n+1);

    for (i = 1; i <= n-2; i++)
        for (j = i+1; j <= n-1; j++)
        {
            st = j+1;   dr = n;     poz = st + (dr-st)/2;
            while (st <= dr)
            {
                mid = st + (dr-st)/2;
                if (v[mid] <= v[i]+v[j])    {   st = mid+1;   poz = mid;   }
                if (v[mid] > v[i]+v[j])     {   dr = mid-1;   }
            }
            if (st > dr && v[poz] <= v[i]+v[j])    nrt += poz-j;
        }
    // 2 3 4 7
    fout << nrt << "\n";
}