Cod sursa(job #1824147)

Utilizator Dupree7FMI Ciobanu Andrei Dupree7 Data 7 decembrie 2016 14:06:45
Problema Numarare triunghiuri Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>

using namespace std;

#define Nmax 800

ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n, v[Nmax];

int BS(int lo, int x)
{
    int hi = n - 1, mid;

    while(hi >= lo)
    {
        mid = lo + (hi - lo) / 2;

        if(x < v[mid])
            hi = mid - 1;
        else if(x > v[mid])
            lo = mid + 1;
        else
            return mid;
    }

    if(lo != n)
        return hi;
    else
        return n - 1;
}

int NrTri()
{
    int i, j, nr = 0;

    for(i = 0; i < n - 2; i++)
        for(j = i + 1; j < n - 1; j++)
            nr = nr + BS(j + 1, v[i] + v[j]) - j;

    return nr;
}

int main()
{
    int i;

    f >> n;

    for(i = 0; i < n; i++)
        f >> v[i];

    sort(v, v + n);
    g << NrTri();

    return 0;
}