Cod sursa(job #1380589)

Utilizator witselWitsel Andrei witsel Data 8 martie 2015 09:14:58
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("ntri.in");
ofstream fout("ntri.out");
int v[801],n,nr;
void check(int st,int dr,int val)
{

    int m,st1=st-1;
    int poz=n+1;
    while(st<=dr)
    {
        m=(dr-st)/2+st;
        if(v[m]>val)
        {
            dr=m-1;
        }
        else
        {
            poz=m;
            st=m+1;
        }

    }
    if(poz<=n)
    nr=nr+(poz-st1);
}
void count()
{
    for(int i=1;i<n-1;++i)
        for(int j=i+1;j<n;++j)
            check(j+1,n,v[i]+v[j]);
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;++i)
        fin>>v[i];
    sort(v+1,v+n+1);
    count();
    cout<<nr;
    /*
    for(int i=1;i<=n;++i)
        cout<<v[i]<<" ";
        */
    return 0;
}