Cod sursa(job #481650)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 1 septembrie 2010 12:12:55
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int N,V[801];

inline int BS(int v)
{
    int st=0,dr=N-1,m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if((V[m]<=v&&V[m+1]>v)||(V[m]<=v&&m==N-1))
            return m;
        else if(V[m]<=v)
            st = m+1;
        else
            dr = m-1;
    }
    return 0;
}
int main()
{
    int nrtri=0,i,j;
    in>>N;
    for(i=0;i<N;i++)
        in>>V[i];
    sort(V,V+N);
    for(i=0;i<N;i++)
        for(j=i+1;j<N;j++)
            nrtri += (BS(V[i]+V[j])-j);
    out<<nrtri;
    return 0;
}