Cod sursa(job #2065701)

Utilizator madalin98Gherghe Madalin madalin98 Data 14 noiembrie 2017 01:09:23
Problema Numarare triunghiuri Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<fstream>
#include<cstdlib>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int hoare(int a[],int p,int r)
{
    int pivot= a[p+(rand()%(r-p+1))],i,j;
    i=p-1;
    j=r+1;
    while(true){
        do{
            ++i;
        }while(a[i]<pivot);
        do{
            --j;
        }while(a[j]>pivot);
        if(i>=j)return j;

        int aux=a[i];
        a[i]=a[j];
        a[j]=aux;
    }
}
void quicksort(int a[],int p,int r){
    if(p<r){
        int q=hoare(a,p,r);
        quicksort(a,p,q);
        quicksort(a,q+1,r);
    }
}
int main()
{
    int v[800],i,n,j,k,nr=0;
    f>>n;
    for(i=0;i<n;i++)
        f>>v[i];
    quicksort(v,0,n-1);
    for(i=0;i<n-2;++i)
        for(j=i+1;j<n-1;++j)
    {
        k=j+1;
        while(v[i]+v[j]>=v[k])
        {
            ++nr;
            ++k;
        }
    }
    g<<nr;
    return 0;
}