Cod sursa(job #613106)

Utilizator Lokycatalin petre Loky Data 16 septembrie 2011 09:47:46
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>

using namespace std;

long int i,j,aux,nr,a[805],st,dr,mij,n,p;

int main()
{
    ifstream f("nrtri.in.");
    ofstream g("nrtri.out.");
    f>>n;
    for (i=1;i<=n;i++)
    f>>a[i];
    for (i=1;i<=n-1;i++)
        for (j=i+1;j<=n;j++)
        if (a[i]>a[j]) {
            aux=a[i];
            a[i]=a[j];
            a[j]=aux;
        }
        nr=0;

        for (i=1;i<=n-2;i++)
              for (j=i+1;j<=n-1;j++) {
                     st=j+1;dr=n;
              while (st<=dr) {   //cautam binar cel mai mare element din vector <= decat suma celorlalte 2 laturi
                     mij=(st+dr)/2;
                     if (a[mij]<=a[i]+a[j]) st=mij+1;
                     else
                     dr=mij-1;
              }
              if (a[mij]<=a[i]+a[j]) //mijlocul ar putea sa nu ne dea chiar acel element ,ci unul care se afla cu o poz peste el -depinde de ce se afla in vector
              nr=nr+mij-j;
              else
              nr=nr+mij-j-1;
              }

            g<<nr;
            f.close();
            g.close();
    return 0;
}