Cod sursa(job #1150322)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 22 martie 2014 20:44:48
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 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 ((v[mid]<=val && v[mid+1]>val) || mid==right)
            return mid;
        if(val>=v[mid]) left = mid+1;
        else right = mid-1;
    }
    cout<<right;
    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++)
        for(int j = i+1 ; j<=n-1; j++)
            sol+=bin_search(v,j,n,v[i]+v[j])-j;
    out<<sol;
    in.close();
    out.close();
    return 0;
}