Cod sursa(job #2438269)

Utilizator Dragos101Baciu Dragos Dragos101 Data 11 iulie 2019 22:15:30
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>

using namespace std;

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

int a[803];

void Merge(int st, int mij, int dr)
{
    int b[800], j, i, k;
    i = st;
    j = mij + 1;
    k = st-1;
    while(i <= mij && j <= dr)
    {
        if(a[i] > a[j]) b[++k] = a[j++];
        else b[++k] = a[i++];
    }
    while(i<=mij)
        b[++k]=a[i++];
    while(j<=dr)
        b[++k]=a[j++];
    for(i=st;i<=dr;i++)
        a[i]=b[i];
}


void Mergesort(int st,int dr)
{
    int mij=(st+dr)/2;
    if(st != dr)
    {
        Mergesort(st,mij);
        Mergesort(mij+1,dr);
        Merge(st,mij,dr);
    }
}

int main()
{
    int n, i, j, k, x, mij, st, dr, tr, poz;
    fin >> n;
    for(i = 1; i <= n; i++)
        fin >> a[i];
    Mergesort(1, n);

    tr = 0;
    for(i = 1; i <= n-2; i++)
        for(j = i + 1; j <= n - 1; j++)
        {
            x = a[i] + a[j];
            st = j + 1;
            dr = n;
            poz=0;
            while(st <= dr)
            {
                mij = (st + dr) / 2;
                if(a[mij] == x)
                {
                    poz = mij;
                    st = mij + 1;
                }
                else
                if(a[mij] > x) dr = mij - 1;
                else {poz = mij; st = mij + 1;}

            }
            if(poz)
                tr += poz-(j+1)+1;
        }
    fout << tr;
    return 0;
}