Cod sursa(job #1166393)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 3 aprilie 2014 15:51:09
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 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, ind2;
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;
                }
            }
            st=j; dr=ind1;
            ind2=-1;
            while (st<=dr) {
                mij=(st+dr)/2;
                if (l1 + lat[mij] >= l2 && l2 + lat[mij] >= l1) {
                    dr=mij-1;
                    ind2=mij;
                }
                else
                    st=mij+1;
            }
            if (ind1 != -1 && ind2!=-1) {
                nrtri+=ind1-ind2+1;
                if (i>=ind2 && i<=ind1)
                    nrtri--;
                if (j>=ind2 && j<=ind1)
                    nrtri--;
            }
        }
    }
    g<<nrtri;
    return 0;
}