Cod sursa(job #1989936)

Utilizator adiailieIlie Adia Elena adiailie Data 9 iunie 2017 17:28:56
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<fstream>
using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n,i,j,st,dr,mid,sol,v[801],aux;

int main() {
    fin>>n;

    for(i=1;i<=n;i++)
        fin>>v[i];

    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
            if(v[i]>v[j]){
                aux=v[i];
                v[i]=v[j];
                v[j]=aux;
            }

    for(i=1;i<=n-2;i++)
        for(j=i+1;j<=n-1;j++){
            //caut cel mai mare k mai mare decat j ai v[k]<=v[i]+v[j]

            st=j+1;
            dr=n;

            while(st<=dr){
                mid=(st+dr)/2;

                if(v[mid]>v[i]+v[j])
                    dr=mid-1;
                else
                    st=mid+1;
            }

            if(v[dr]<=v[i]+v[j])
                sol+=dr-j;
        }

    fout<<sol;
}