Cod sursa(job #1197706)

Utilizator gbibBacotiu Gabi gbib Data 13 iunie 2014 14:18:29
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int n,i,j,cont,v[801],sol;
int bs(int st,int dr,int x)
{
    int mij;
    while (st<=dr) {
        mij=(st+dr)>>1;
       if (v[mij]>x)
       dr=mij-1;
       else
       st=mij+1;
    }
    return dr;
}
int main()
{
in>>n;
for(i=1;i<=n;i++)
    in>>v[i];
sort (v+1,v+n+1);
for(i=1;i<=n;i++)
{
    for(j=i+1;j<=n;j++)
    {
        sol=sol+bs(j,n,v[i]+v[j])-j;
    }
}
out<<sol<<'\n';
    return 0;
}