Cod sursa(job #1691064)

Utilizator eddie.deaconuDeaconu Stefan-Eduard eddie.deaconu Data 16 aprilie 2016 19:12:07
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <iostream>
#include <algorithm>
#include <fstream>

using namespace std;

int v[801],n;
ifstream f("nrtri.in");
ofstream g("nrtri.out");

int cautbin(int x, int st, int dr)
{
    int m;
    while (st<=dr)
    {
        m=(st+dr)/2;
        if (v[m]>=x) dr=m-1;
        else st=m+1;
    }
    if (v[m]<x) return m+1;
    return m;
}

int main()
{
    int i,j;

    f>>n;
    for (i=1; i<=n; i++)
        f>>v[i];
    f.close();

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

    int nr=0;
    for (i=1; i<=n-1; i++)
    {
        for (j=n; j>=(i+2); j--)
        {
            nr+=j-cautbin(v[j]-v[i],i+1,j-1);
        }
    }
    g<<nr;
    g.close();
    return 0;
}