Cod sursa(job #2961896)

Utilizator popica312Pop David-Gabriel popica312 Data 7 ianuarie 2023 12:28:53
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin("nrtri.in");
ofstream cout("nrtri.out");

int N, v[800], i, total;

int caut_binar(int sum, int j, int st, int dr)
{
     while (st < dr)
     {
         int sumMed = (v[st] + v[dr])/ 2;
         if (sum >= sumMed)
         {
              dr = (dr+st) / 2;
         }
         else
         {
              st = (dr+st) / 2 + 1;
         }
     }
     return dr - j;
}

int main()
{
     cin >> N;
     for (i = 0; i < N; ++i)
     {
         cin >> v[i];
     }
     sort (v, v+N);
     for (i = 0; i < N - 2; ++i)
     {
          for (int j = i + 1; j < N - 1; ++j)
          {
               int sum = v[i] + v[j];
               total = total + caut_binar(sum, j, j+1, N-1);
          }
     }
     cout << total / 2 + 1;
     return 0;
}