Cod sursa(job #2074363)

Utilizator novistaAlex Staicu novista Data 24 noiembrie 2017 15:24:50
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define Nmax 809
using namespace std;
ifstream fin ("nrtri.in");
ofstream fout ("nrtri.out");
int n,v[Nmax],k,s;
unsigned long long con;
int bin_search(int p,int u)
{
    int m;
    if (p>u)
        return 0;
    else
    {
        m=(p+u)/2;
        if (v[m]<=s&&v[m+1]>s)
            return m;
        else if (v[m]<=s)
                return bin_search(m+1,u);
             else return bin_search(p,m-1);
    }
}
int main()
{
    int p,u,i,j;
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];
    sort(v+1,v+n+1);
    v[n+1]=80000;
    for (i=1;i<=n-2;i++)
    {
        for (j=i+1;j<=n-1;j++)
        {
            p=j+1;
            u=n;
            s=v[i]+v[j];
            k=bin_search(p,u);
         //   if (i==4&&j==5) cout<<k<<" ";
            if (k!=0)
            {
                con=con+k-j;
             //   cout<<i<<" "<<j<<" "<<k<<"\n";
            }
        }
    }
    fout<<con<<"\n";
    fin.close();
    fout.close();
    return 0;
}