Cod sursa(job #1850479)

Utilizator alexkolumeRadulescu Ioan-Alexandru alexkolume Data 18 ianuarie 2017 18:12:01
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("nrtri.in");
ofstream fout ("nrtri.out");
vector <int> v;
int main()
{
    int n ,i ,j ,mid = 0 ,a = 0 ,s = 0 ,st ,dr, temp;
    fin >> n;
    v.resize(n + 1);
    for(i = 1 ;i <= n ;i++)
      fin >> v[i];
    sort(v.begin(),v.end());
    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;
            while(st <= dr)
            {
                if((v[mid] <= a && a < v[mid + 1] ) || (v[mid] <= a && mid == n))
                {
                    s+=(mid -  j);
                    break;
                }
                if(v[mid] <= a)
                    st = mid + 1;
                if(a < v[mid])
                    dr = mid - 1;
                mid = (st+dr)/2;
            }
        }
    fout<<s;
    return 0;
}