Cod sursa(job #2075154)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 25 noiembrie 2017 11:34:54
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int stixlen;
int stix[841];

int binSearch(int n, int lg)
{
    int pos = 0;
    for(; lg > 0; lg >>= 1){
        if(pos + lg <= stixlen){
            if(stix[pos + lg] <= n){
                pos += lg;
            }
        }
    }
    return pos;
}

int invBinSearch(int n, int lg)
{
    int pos = stixlen;
    for(; lg > 0; lg >>= 1){
        if(pos - lg > 0){
            if(stix[pos - lg] >= n){
                pos -= lg;
            }
        }
    }
    return pos;
}

int findValidTriangles(int first, int last, int lg)
{
    int smallest = stix[last] - stix[first];
    int biggest = stix[first] + stix[last];
    int r = binSearch(biggest, lg) - invBinSearch(smallest, lg);
    if(smallest < stix[first]){
        r--;
    }
    if(biggest > stix[last]){
        r--;
    }
    return max(r, 0);
}

int main()
{
    ifstream fin("nrtri.in");
    ofstream fout("nrtri.out");
    int validTriangles = 0, lg;
    fin >> stixlen;
    for(lg = 1; lg <= stixlen; lg <<= 1);
    for(int i = 1; i <= stixlen; i++){
        fin >> stix[i];
    }
    sort(stix + 1, stix + stixlen + 1);
    /*
    for(int i = 1; i <= stixlen; i++){
        cout << stix[i] << " ";
    }
    */
    for(int i = 1; i <= stixlen; i++){
        for(int j = i + 1; j <= stixlen; j++){
            //cout << findValidTriangles(i, j, lg) << " ";
            validTriangles += findValidTriangles(i, j, lg);
        }
    }
    fout << validTriangles;
    return 0;
}