Cod sursa(job #1669798)

Utilizator andreipurdilaAndrei Purdila andreipurdila Data 31 martie 2016 03:16:10
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int binarySearch(int lo, int  hi, int key, vector<int> values) {
    int mid;
    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;
        if (values[mid] == key) {
            return mid;
        } else if (values[mid] < key) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }

    }
    return -1;
}


int main()
{
    ifstream f("nrtri.in");
    ofstream g("nrtri.out");

    int n;
    f>>n;
    vector<int> lengths;
    while (n) {
        int length;
        f>>length;
        lengths.push_back(length);
        n--;
    }

    sort(lengths.begin(), lengths.end());

    int possibleTr = 0;
    for (int i = 0; i < lengths.size(); ++i) {
        for (int j = i + 1; j < lengths.size(); ++j) {
            int sum = lengths[i] + lengths[j];
            for (int k = sum; k > 0; --k ) {
                int pos = binarySearch(j+1, lengths.size()-1, k, lengths);
                if (pos != -1 && pos != i && pos != j) {
                    if (lengths[i] + lengths[pos] >= lengths[j] && lengths[j] + lengths[pos] > lengths[i]){
                        possibleTr++;
                    }
                }
            }
        }
    }
    g<<possibleTr;
    f.close();
    g.close();
}