Cod sursa(job #1520330)

Utilizator SoniaFlorinaHorchidan Sonia-Florina SoniaFlorina Data 8 noiembrie 2015 16:49:44
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int n, v[800],nr;

 int Divide(int p, int q)
 { int st=p,dr=q,x=v[p];
 while(st<dr)
 {
     while(st<dr && v[dr]>=x)
        dr--;
     v[st]=v[dr];
     while(st<dr && v[st]<=x)
        st++;
     v[dr]=v[st];}
v[st]=x;
return st;
 }


 void qsort(int p, int q)
{ int m=Divide(p,q);
if(p<m)
        qsort(p,m-1);
    if(m<q)
        qsort(m+1,q);
}


/*int cautare(int i, int j, int li, int ls)
{ if(li>ls)
    return -1;
else
    {int mij=(li+ls)/2;
    if((v[mij]<=v[i]+v[j] && v[mij+1]>=v[i]+v[j]) || (mij==n&& v[mij]<=v[i]+v[j]))
    //if((v[mij]<=v[i]+v[j] && v[mij+1]>=v[i]+v[j]) && (v[mij]+v[i]<=v[j] && v[mij+1]+v[i]<=v[j]) && (v[mij]+v[j]<=v[i] && v[mij+1]+v[j]<=v[i]))
        return mij;
    else
        return cautare(i,j,mij+1,ls);
    }
}*/

int main()
{int i,j,k;
in>>n;
for(i=1;i<=n;i++)
    in>>v[i];

qsort(1,n);
int ok=1;
for(i=1;i<=n-1;i++)
    for(j=i+1;j<=n-1;j++)
        /*{int poz=cautare(i,j,j+1,n);
        //cout<<poz<<' ';
        if(poz!=-1)
            nr+=n-poz+1;*
        }*/
        {ok=1;
        for(k=j+1;k<=n &&ok;k++)
            if(v[i]+v[j]<=v[k])
                ok=0;
        nr+=n-k+1;}

out<<nr;
in.close();
out.close();




    return 0;
}