Cod sursa(job #2202375)

Utilizator eduardandrei20Nechifor Eduard Andrei eduardandrei20 Data 8 mai 2018 17:12:20
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;
int v[801];
 int n ;
  void Inputu()
  {
      freopen("nrtri.in","r",stdin);
         cin >> n ;
             for(int i =1; i<=n ;++i)
             {
                 cin>>v[i];
             }
             sort(v+1,v+n+1);
  }

  inline bool triunghi (int a, int b, int c)
  {
      if(a+b>=c and a+c>=b and b+c>=a)return true;
            return false;
  }

  int caut_pozitia( int ST, int DR )
  {   int latura1=v[ST];
  int latura2=v[DR];
       int poz = -1;
       // cea mai din dreapta care merge sa fac un triunghi
         int st=DR+1 , dr=n;
             while(st<=dr )
             {
                 int m = (st+dr)>>1;
                    if(triunghi(latura1,latura2,v[m]))
                    {
                        poz=m;
                        st=m+1;
                    }
                    else
                    {
                        dr=m-1;
                    }
             }
             if(poz==-1)return 0;
      return poz-DR;
  }


int main()
{
    Inputu();
        int rez= 0;
        for(int i =1; i <=n-2; ++i)
            for(int j =i +1 ; j<=n-1; ++j)
            rez+=caut_pozitia(i,j);
        freopen("nrtri.out","w",stdout);
        cout<<rez;



    return 0;
}