Cod sursa(job #2162171)

Utilizator victorv88Veltan Victor victorv88 Data 12 martie 2018 08:41:02
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <bits/stdc++.h>

std::ifstream f("nrtri.in");
std::ofstream g("nrtri.out");

using namespace std;

int n, a[805],st,dr,x,y,mij,nr;
int val;


int cautbin(int val)
{
    int st=1, dr=n, mij, poz=0;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (a[mij]<val)
            st=mij+1;
        else
            dr=mij-1;
    }
    return (st+dr)/2;
}

int main()
{
    f >> n;
    for (int i=1; i<=n; i++)
        f >> a[i];
    sort(a+1,a+1+n);
    for (int i=1; i<=n-2; i++)
    {
        for (int j=i+2; j<=n; j++)
        {
            val=a[j]-a[i];
            nr+=j-i-cautbin(val);
        }
    }
    g << nr;
    return 0;
}