Cod sursa(job #1517450)

Utilizator RobertGCARezeanu Robert Gabriel Cristian Alexandru RobertGCA Data 4 noiembrie 2015 12:25:02
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n, i, v[801], j, x, s, st, dr, mid, suma;
int main () {
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];

    sort(v+1, v+n+1);

    for(i=1;i<=n-2;i++)
        for(j=i+1;j<=n;j++) {
            st=j+1;
            dr=n;

            suma=v[i]+v[j];

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

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

            if(v[st]<suma)
                s+=st-j;
        }


    fout<<s;

    return 0;
}