Cod sursa(job #2168416)

Utilizator SternulStern Cristian Sternul Data 14 martie 2018 10:52:41
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int nr, a[808], n;

int divide(int p, int q)
{
    int st = p, dr = q, x = a[p];
    while(st < dr){
        while(st < dr && a[dr] >= x)
            dr--;
        a[st] = a[dr];
        while(st < dr && a[st] <= x)
            st++;
        a[dr] = a[st];
    }
    a[st] = x;
    return st;
}

void QSort(int p,int q)
{
    int m = divide(p,q);
    if(m - 1 > p)
        QSort(p, m - 1);
    if(m + 1 < q)
        QSort(m + 1, q);
}

void afisare()
{
    for(int i = 1;i <= n;i ++)
        cout<<a[i]<<" ";
}

void citeste()
{
    f>>n;
    for(int i = 1;i <= n;i ++)
        f>>a[i];
    QSort(1, n);
}

int bsearch(int x,int s)
{
    int dr = n, st = s, mid;
    while(st<=dr)
    {
        mid = (st + dr) / 2;
        if(a[mid] > x)
            dr = mid  - 1;
        else st = mid + 1;
    }
    return dr - s;
}

void solve()
{
    for(int i = 1; i <= n - 2;i++)
        for(int j = i + 1;j <= n - 1;j++)
            nr+=bsearch(a[i] + a[j],j);
}

int main()
{
    citeste();
    solve();
    g<<nr;
    return 0;
}