Cod sursa(job #1374242)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 5 martie 2015 00:45:00
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <algorithm>
#define DIM 1024
using namespace std;

ifstream fin ("nrtri.in" );
ofstream fout("nrtri.out");

int N, i, j, V[DIM], pos1, pos2, nr;
int a, b, mid;

void Set_Up(){
     fin >> N;
     for(i = 1; i <= N; i ++)
          fin >> V[i];
     sort(V + 1, V + N + 1);
     return;
}

void Binary_Search(){
     for(i = 1; i <= N-2; i ++)
          for(j = i + 1; j < N; j ++){
               /*
                    DETERMIN CU CAUTARE BINARA
                      max(j + 1, V[j] - V[i])
               */
               a = j + 1; b = N;
               while(a <= b){
                    mid = a + (b - a) / 2;
                    if(V[mid] >= V[j] - V[i])
                         b = mid - 1;
                    else
                         a = mid + 1;
               }
               pos1 = a;
               a = j + 1; b = N;
               while(a <= b){
                    mid = a + (b - a) / 2;
                    if(V[mid] <= V[j] + V[i])
                         a = mid + 1;
                    else
                         b = mid - 1;
               }
               pos2 = b;
               nr += pos2 - pos1 + 1;
          }
     fout << nr;
     return;
}

int main(){
     Set_Up();
     Binary_Search();
     return 0;
}