Cod sursa(job #1837170)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 29 decembrie 2016 09:37:23
Problema Numarare triunghiuri Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in ("nrtri.in");
ofstream out ("nrtri.out");
vector <int> v;
int main()
{
    int n ,i ,j ,mid = 0 ,a = 0 ,s = 0 ,st ,dr ;
    in>>n;
    v.resize(n + 1);
    for(i = 1 ;i <= n ;i++){
      in>>v[i];
    }
    sort(v.begin(),v.end());
    ///v[n + 1] = 30001;
    for(i = 1 ; i <= n - 2 ;i++){
      for(j = i + 1 ; j <= n - 1 ;j++){
        a = v[j]+v[i];
        st = j + 1;
        dr = n;
        mid = (st+dr)/2;
        //cout<<a<<" "<<v[mid]<<" ";
        while(st <= dr){
          if((v[mid] <= a && a < v[mid + 1] )){
            s+=(mid -  j);
            //cout<<v[mid]<<" "<<v[j]<<" "<<v[i]<<" "<<(mid - j);
            break;
          }
          if(v[mid] <= a){
            st = mid + 1;
          }
          if(a < v[mid]){
            dr = mid - 1;
          }
          mid = (st+dr)/2;
          //cout<<mid<<" ";
        }
        //cout<<'\n';
      }
    }
   // cout<<":";
    out<<s;
    return 0;
}