Cod sursa(job #1166396)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 3 aprilie 2014 15:54:21
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
#include <algorithm>
#define NMax 801
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n, lat[NMax], st, dr, mij, i, j, l1, l2, nrtri, ind1;
int main()
{
    f>>n;
    for (i=1; i<=n; i++)
        f>>lat[i];
    sort(lat + 1, lat + n + 1);
    for (i=1; i<=n; i++) {
        for (j=i+1; j<=n; j++) {
            l1=lat[i];
            l2=lat[j];
            st=j;
            dr=n;
            ind1=-1;
            while (st<=dr) {
                mij=(st+dr)/2;
                if (lat[mij] > l1 + l2)
                    dr=mij-1;
                else {
                    ind1=mij;
                    st=mij+1;
                }
            }
            nrtri+=ind1-j;
        }
    }
    g<<nrtri;
    return 0;
}