Cod sursa(job #1525633)

Utilizator goalexboxerFMI Alexandru Ionascu goalexboxer Data 15 noiembrie 2015 12:18:21
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#define FIN "nrtri.in"
#define FOUT "nrtri.out"
#define MAXN 801
using namespace std;


ifstream f(FIN);
ofstream g(FOUT);

int v[MAXN];
int n;



bool isTriangle(int a, int b, int c)
{
    if( a + b >= c &&  a + c >= b && b + c >= a)
        return true;
    else return false;
}

int search(int a, int b, int left, int right)
{

    if(left > right)
    {
        return -1;
    }
    else
    {
        if(right - left <= 1)
        {
            if(isTriangle(a, b, v[left]))
                return left;
            if(isTriangle(a, b, v[right]))
                return right;
            return -1;
        }
        else
        {
            int mid = (left + right) / 2;
            if(isTriangle(a, b, v[mid]))
            {
                search(a, b, mid, right);
            }
            else
            {
                search(a, b, left, mid);
            }

        }
    }

}



int main()
{
    f >> n;
    int counter = 0;
    for(int i=1; i<=n; i++)
        f >> v[i];

    sort(v + 1, v + n + 1);

    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            int index = search(v[i], v[j], j+1, n);
            if(index != -1)
                counter = counter + index - j;
        }
    }

    g << counter;

    return 0;

}