Cod sursa(job #2522244)

Utilizator As932Stanciu Andreea As932 Data 12 ianuarie 2020 10:54:39
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n;
int bat[801];
int nrTri=0;

void binary_s(int i, int j)
{
    int l=j+1,r=n,mid,sol=-1;

    while(l<=r)
    {
        mid=(l+r)/2;
        if(bat[mid]<=bat[i]+bat[j])
        {
            sol=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    if(sol!=-1)
        nrTri+=sol-j;

}

int main()
{
    fin>>n;

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

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

    for(int i=1;i<n-1;i++)
        for(int j=i+1;j<n;j++)
            binary_s(i,j);

    fout<<nrTri;

    return 0;
}