Cod sursa(job #1150308)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 22 martie 2014 20:25:31
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<fstream>
#include<iostream>
using namespace std;

void quicksort(int v[],int left,int right)
{
    int i=left,j=right,pivot,aux;
    pivot = v[(i+j)/2];
    while(i<=j)
    {
        while(v[i]<pivot) i++;
        while(v[j]>pivot) j--;
        if(i<=j)
        {
            aux = v[i];
            v[i] = v[j];
            v[j] = aux;
            i++;
            j--;
        }
    }
    if(left<j) quicksort(v,left,j);
    if(right>i) quicksort(v,i,right);
}

int bin_search(int v[],int left,int right,int val)
{
    int mid;
    while(left<=right)
    {
        mid = (left+right)/2;
        if(val>=v[mid]) left = mid+1;
        else right = mid-1;
    }
    return right;
}

int main()
{

    ifstream in("nrtri.in");
    ofstream out("nrtri.out");
    int i,n,v[1000],sol=0;
    in>>n;
    for( i = 1 ; i <= n ; i++)
        in>>v[i];
    quicksort(v,1,n);
    for(i = 1 ; i<=n-2 ; i++)
        sol+=bin_search(v,1,n,v[i]+v[i+1])-(i+1);
    out<<sol;
    in.close();
    out.close();
    return 0;
}