Cod sursa(job #1521728)

Utilizator ArmandNMArmand Nicolicioiu ArmandNM Data 10 noiembrie 2015 19:53:13
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <algorithm>

const int NMAX = 1000;

using namespace std;

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

int N;
int v[NMAX];
int ans;
int x;

int cautare(int v[], int ls, int ld, int val)
{
    int mid;
    int pos = 0;

    while(ls <= ld)
    {
        mid = (ls + ld) / 2;
        if (v[mid] <= val)
        {
            pos = mid;
            ls = mid + 1;
        }
        else
        {
            ld = mid - 1;
        }
    }

    return pos;
}

int main()
{
    f >> N;

    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)
        {
            x = cautare(v,j+1,N,v[i]+v[j]);
            if (x)
            {
                ans += (x-j);
                x = 0;
            }
        }
    }

    g << ans << '\n';

    return 0;
}