Cod sursa(job #1520349)

Utilizator SoniaFlorinaHorchidan Sonia-Florina SoniaFlorina Data 8 noiembrie 2015 17:09:52
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int n, v[805],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 main()
{int i,j,stg,dr,mij;
in>>n;
for(i=1;i<=n;i++)
    in>>v[i];
qsort(1,n);
for(i=1;i<=n-1;i++)
    for(j=i+1;j<=n;j++)
        {stg=j;
        dr=n+1;
        while(dr-1>stg)
            {mij=(stg+dr)/2;
            if(v[mij]<=v[i]+v[j])
                stg=mij;
            else
                dr=mij;
            }
            if(stg<=n)
                nr+=n-stg;
            }

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

    return 0;
}