Cod sursa(job #2061569)

Utilizator Andreiii500Andrei Puiu Andreiii500 Data 9 noiembrie 2017 14:45:23
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include<algorithm>
#include<iostream>
#include<fstream>
using namespace std;

ifstream in("nrtri.in");
ofstream out("nrtri.out");

const int N = 800;
int v[N];
int n;

int indexOf(int x){
    int left = 0;
    int right = n-1;
    while(left != right){
        int middle = (left + right) / 2;

        if(x <= v[middle])
            right = middle;
        else /// (x > v[middle])
            left = middle+1;
    }
    return left;
}

int compare(int a, int b){ return a < b; }

int main()
{
    int sol = 0;

    in>>n;
    for(int i=0; i<n; ++i)
        in>>v[i];

    sort(v, v+n, compare);
    ///for(int i=0; i<n; ++i) cout<<v[i]<<" "; cout<<"\n";

    for(int firstIndex = 0; firstIndex < n; ++firstIndex)
        for(int secondIndex = firstIndex + 1; secondIndex < n; ++secondIndex)
        {
            int thirdEdgeMaximalValue = v[firstIndex] + v[secondIndex];
            int thirdIndex = indexOf(thirdEdgeMaximalValue);
            while(thirdIndex < n-1  &&  v[thirdIndex+1] <= thirdEdgeMaximalValue)
                ++thirdIndex;
            while(thirdIndex > 0  &&  v[thirdIndex] > thirdEdgeMaximalValue)
                --thirdIndex;

            int possibleEdgeLength = (thirdIndex - secondIndex);
            if(possibleEdgeLength > 0)
            {
                sol += possibleEdgeLength;
                ///cout<<v[firstIndex]<<" "<<v[secondIndex]<<" --> index = "<<thirdIndex<<"\n";
            }
        }
    out<<sol;

    return 0;
}