Cod sursa(job #1824142)

Utilizator Dupree7FMI Ciobanu Andrei Dupree7 Data 7 decembrie 2016 14:03:25
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 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 valid(int a, int b, int c)
{
    return (a <= b + c && b <= a + c && c <= a + b && a >= abs(b - c) && b >= abs(c - a) && c >= abs(a - b)) ? 1 : 0;
}

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, k;

    for(i = 0; i < n - 2; i++)
        for(j = i + 1; j < n - 1; j++)
            nr = nr + BS(j, 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);
    cout << NrTri();

    return 0;
}