Cod sursa(job #2769266)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 14 august 2021 13:48:54
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;

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

int n,v[805],ans;

int main()
{
    fin>>n;

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

    sort(v+1,v+n+1); //pointer+intreg e ok, dar intreg+pointer nu e ok  O(n log n) sortarea din STL


    /**
        Daca laturile triunghiului sunt v[i]<v[j]<v[k] atunci v[i]+v[j]>=v[k], i<j<k
    **/

    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
    {
        int st=j+1;
        int dr=n;
        int sol=-1;

        while(st<=dr)
        {
            int mid=(st+dr)/2;
            if(v[mid]<=v[i]+v[j])
            {
                sol=mid;
                st=mid+1;
            }
                else dr=mid-1;
        }

        if(sol!=-1)
            ans+=sol-j; //[j+1,sol]
    }

    fout<<ans<<'\n';
    return 0;
}