Cod sursa(job #2472482)

Utilizator amalia.gemanGeman Aamalia amalia.geman Data 12 octombrie 2019 14:12:50
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n,a[801];

bool Triunghi(int a, int b, int c)
{
    if(a+b>=c && a+c>=b && b+c>=a)
        return 1;
    else
        return 0;
}

int CautBin(int x,int y)
{
    int m,st,dr,sol=-1;
    st=y+1;
    dr=n;

    while(st<=dr)
    {
        m=(st+dr)/2;
        if(Triunghi(a[x],a[y],a[m]))
        {
            sol=m;
            st=m+1;
        }
        else dr=m-1;
    }

    return sol;
}

int main()
{
    int ct=0;

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

    sort(a,a+n+1);


    //rezolvare
    for(int i=1;i<=n-2;i++)
       for(int j=i+1;j<=n-1;j++)
      { int nr=CautBin(i,j);
        if(nr!=-1)
          ct+=nr-j;
      }

    fout<<ct;

    fin.close();
    fout.close();
    return 0;
}