Cod sursa(job #2967483)

Utilizator PHOSSESSEDProsie Radu-Teodor PHOSSESSED Data 19 ianuarie 2023 18:00:43
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> v;;

int bin(int st,int dr,int val)
{
    ///laturile triunghilui respecta a + b >= c
    ///caut prima pozitie ai v[p] < val;

    int ans = -1;
    while(st <= dr)
        {
            int mid = st + (dr - st) / 2;
            if(v[mid] <= val)
                {
                    ans = mid;
                    st = mid + 1;
                }

            else dr = mid - 1;
        }

    return ans;
}

int main()
{
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);

    int n; cin >> n; v.resize(n + 1);
    for(int i = 1; i <= n ; i++) cin >> v[i];
    sort(v.begin() + 1,v.end());

    int ans = 0;

    for(int i = 1; i < n - 1; i++)
        {
            for(int j = i + 1; j < n ; j++)
                {
                    int cate = bin(1,n,v[i] + v[j]);
                    ans += cate - j;
                }
        }

    cout << ans;

}