Cod sursa(job #1049508)

Utilizator DGVanceaDragos Gabriel Vancea DGVancea Data 7 decembrie 2013 13:44:35
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("ntri.in");
ofstream fout("ntri.out");

void partitionare(int i,int j,int &k,int v[])
{
    int si=0,sj=-1;
    while(i<j)
    {
        if(v[i]>v[j])
        {
            swap(v[i],v[j]);
            int aux=si;
            si=-sj;
            sj=-aux;
        }
        i+=si;
        j+=sj;
        k=i;
    }


}

void sortare(int i,int j,int v[])
{
    int k;
    if(i<j)
    {
        partitionare(i,j,k,v);
        sortare(i,k-1,v);
        sortare(k+1,j,v);
    }
}

int cb(int v[],int n)
{int nr=0;
    for(int i=1;i<n-1;i++)
        for(int j=i+1;j<n;j++)
          for(int k=j+1;k<=n;k++)
              if(v[i]+v[j]>=v[k])nr++;
              else break;
    return nr;
}

int main()
{
   int n;
   fin>>n;
   int v[n+1];
   for(int i=1;i<=n;i++)
    fin>>v[i];
   sortare(1,n,v);
fout<<cb(v,n);
    return 0;
}