Cod sursa(job #2886618)

Utilizator dfettiDaniel Fetti dfetti Data 7 aprilie 2022 22:53:17
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

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

#define DIM 801

int n;
int A[DIM];

inline void swap(int* a, int* b)
{
    int aux = *a;
    *a = *b;
    *b = aux;
}

int partition(int* v, int lo, int hi)
{
    int pivot = v[hi];
    int i = lo - 1;

    for (int j = lo; j <= hi - 1; ++j)
    {
        if (v[j] < pivot)
        {
            i++;
            swap(&v[i], &v[j]);
        }
    }

    swap(&v[i + 1], &v[hi]);
    return i + 1;
}

void quic_sort(int* v, int lo, int hi)
{
    if (lo >= hi)
        return;

    int p = partition(v, lo, hi);
    quic_sort(v, lo, p - 1);
    quic_sort(v, p + 1, hi);
}

int binary_search(int lo, int hi, int x)
{
    int med = 0;
    while (hi - lo > 1)
    {
        med = (hi + lo) / 2;

        if (x < A[med])
            hi = med;
        else
            lo = med;
    }

    return lo;
}

int main()
{
    fin >> n;
    for (int i = 0; i < n; ++i)
        fin >> A[i];

    quic_sort(A, 0, n - 1);

    /*for (int i = 0; i < n; ++i)
        cout << A[i] << ' ';
    cout << '\n';*/

    int count = 0;
    for (int i = 0; i < n - 1; ++i)
        for (int j = i + 1; j < n - 1; ++j)
        {
            int ma = A[i] + A[j];
            int p = binary_search(j + 1, n - 1, ma);
            if (A[p] > ma) p--;
            
            count += p - j;
            /*cout << "A[i]=" << A[i] << " ";
            cout << "A[j]=" << A[j] << " ";
            cout << "ma=" << ma << " ";
            cout << "p=" << p << " ";
            cout << "count=" << count << " ";
            cout << '\n';*/
        }

    fout << count;

    return 0;
}