Cod sursa(job #2602371)

Utilizator GeorgeCalinPetruta George-Calin GeorgeCalin Data 16 aprilie 2020 19:40:08
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>
#include <algorithm>
#define nmax 30005
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int mai_mare[nmax];
int mai_mic[nmax];
int nr_bete[nmax];
int bat[805];

int main()
{
    int numar_bete;
    fin >> numar_bete;
    for(int i = 1; i <= numar_bete; i++)
    {
        fin >> bat[i];
        nr_bete[bat[i]]++;
    }
    sort(bat + 1, bat + numar_bete + 1);
    for(int i = 1; i <= 30000; i++)
    {
        mai_mic[i] += mai_mic[i - 1] + nr_bete[i];
    }
    int solutie = 0;
    for(int i = 1; i < numar_bete; i++)
    {
        for(int j = i + 1; j < numar_bete; j++)
        {
            int limita_sus = bat[j] + bat[i];
            int dreapta = numar_bete;
            int stanga = j + 1, mijloc;
            int gasit = 0;
            while(!gasit && dreapta >= stanga)
            {
                mijloc = (dreapta + stanga) / 2;
                if(bat[mijloc] == limita_sus)
                {
                    while(bat[mijloc] == limita_sus)
                        mijloc++;
                    gasit = 1;
                    mijloc--;
                }
                else
                {
                    if(bat[mijloc] > limita_sus)
                    {
                        dreapta = mijloc - 1;
                    }
                    else
                    {
                        stanga = mijloc + 1;
                    }
                }
            }
            if(!gasit)
            {
                if(bat[mijloc] > limita_sus)
                {
                    while(bat[mijloc] > limita_sus)
                        mijloc--;
                }
                else
                {
                    while(bat[mijloc] < limita_sus && mijloc <= numar_bete)
                        mijloc++;
                    mijloc--;
                }
            }
            solutie += mijloc - j;
        }
    }
    fout << solutie;
    return 0;
}