Cod sursa(job #1455396)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 27 iunie 2015 21:49:27
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("nrtri.in");
ofstream out("nrtri.out");
int n;
long int sol = 0;
vector <int> a;

void quicksort(int x,int y)
{
    if(x<y)
    {
        int i=x,j=y,pivot = a[x];
        while(i<j)
        {
            if(a[i]>a[j])
            {
                int h= a[i];
                a[i] = a[j];
                a[j] = h;
            }
            if(a[i] == pivot)
                j--;
            else
                i++;
        }
        int m =i;
        quicksort(x,m-1);
        quicksort(m+1,y);
    }

}

int bin_search(int x,int y,int val)
{
    if(x<=y)
    {
        int m = (x+y)/2;
        if(((a[m]<=val)&&(a[m+1]>val))||(m==a.size()-1))
            return m;
        else
        {
            if(a[m]>val)
            return bin_search(x,m-1,val);
        else
            return bin_search(m+1,y,val);
        }
    }
}

int main()
{
    in>>n;
    int x;
    in.close();
    for(int i=1;i<=n;i++)
    {
        in>>x;
        a.push_back(x);
    }
    quicksort(0,a.size()-1);
    for(int i =0;i<a.size()-1;i++)
    {
        int x = bin_search(i+1,a.size()-1,a[i]+a[i+1]);
        int y = x-i-1;
        if(y>0)
            sol+=y;
    }
    out<<sol;
    out.close();
    return 0;
}