Cod sursa(job #1346861)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 18 februarie 2015 17:35:27
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <algorithm>
const int maxn=2005;
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int v[maxn];
int cautbin(int x,int n)
{
    int st=1;
    int dr=n + 1;
    while(dr-st>1)
    {

        int mij=(st+dr)/2;
        if(v[mij]<=x)
        {
            st=mij;
        }
        else if(v[mij]>x)
        {
            dr=mij;
        }

    }
    return st;
}
int main()
{
    int n;
    in>>n;

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

    sort(v+1,v+n+1);
    v[n + 1] = 100000000;
    int nr=0;

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