Cod sursa(job #2036684)

Utilizator ZarisZaris Neamtiu Zaris Data 10 octombrie 2017 22:31:20
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>
#include <cmath>
#include <tgmath.h>
using namespace std;

int a[801];

int cautare2(int l,int r, int v)
{
    int m, poz{-1};

    while (l <= r)
    {
        m = (l + r) / 2;

        if (a[m] <= v)
            l = m + 1, poz = m;

        else r = m - 1;
    }

    return poz;
}

int cautare3(int l, int r, int v)
{
    int m, poz{-1};
    while (l <= r)
    {
        m = (l + r) / 2;
        if (a[m] >= v)
            r = m - 1, poz = m;
        else
            l = m + 1;
    }
    return poz;
}

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

    int n, cnt = 0;

    fin >> n;

    for(int i = 1; i <= n; ++i)
        fin >> a[i];

    sort(a + 1, a + n + 1);

    int i1, i2;

    for(int i = 1; i <= n - 1; ++i)
        for(int j = i + 1; j <= n; ++j)
        {
            i1 = cautare2(j + 1, n, a[i] + a[j]);
            i2 = cautare3(j + 1, n, abs(a[i] - a[j]));

            if(i1 != -1 && i2 != -1)
                cnt += i1 - i2 + 1;
        }

    fout << cnt;

    return 0;
}