Cod sursa(job #1837069)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 28 decembrie 2016 23:09:54
Problema Numarare triunghiuri Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 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 = 3 ; i <= n ;i++){
      for(j = 2 ; j < i ;j++){
        a = v[i]-v[j];
        st = 1;
        dr = j;
        mid = (st+dr)/2;
        //cout<<a<<" "<<v[mid]<<" ";
        while(true){
          if((mid == 0 && a < v[mid]) || mid == j){
            break;
          }
          if((v[mid] < a && a <= v[mid + 1]  && mid != j)){
            s+=(j-mid - 1);
            //cout<<v[mid + 1]<<" "<<v[j]<<" "<<v[i]<<" "<<(j-mid- 1);
            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;
}