Cod sursa(job #1793873)

Utilizator teo.cons98Constantin Teodor-Claudiu teo.cons98 Data 31 octombrie 2016 17:11:41
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include<iostream>
#include<fstream>
#include<cmath>
using namespace std;
int v[801][2], A[801][2], n, suma, diferenta, prim, last;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

void citire()
{
    fin>>n;
    for(int i = 1; i <= n; ++i)
    {
        fin>>v[i][1];
        v[i][0] = i;
    }
}

void sortare(int p, int u)
{
    if(p < u)
    {
        int p1 = p;
        int mid = (p + u) / 2 , mid1 = mid + 1, t, x = p1;
        sortare(p,mid);
        sortare(mid + 1,u);
        while(p <= mid and mid1 <= u)
        {
            if(v[p][1] <= v[mid1][1])
            {
                A[x][1] = v[p][1];
                A[x][0] = v[p][0];
                ++x;
                ++p;
            }
            else
            {
                A[x][1] = v[mid1][1];
                A[x][0] = v[mid1][0];
                ++mid1;
                ++x;
            }
        }
        while(p <= mid)
        {
            A[x][1] = v[p][1];
            A[x][0] = v[p][0];
            ++x;
            ++p;
        }

        while(mid1 <= u)
        {
            A[x][1] = v[mid1][1];
            A[x][0] = v[mid1][0];
            ++x;
            ++mid1;
        }
        for(int i = p1; i <= u; ++i)
        {
            v[i][1] = A[i][1];
            v[i][0] = A[i][0];
        }
    }
}

void cautbin1(int p, int u)
{
    if(p <= u)
    {
        int mid = (p + u) / 2;
        if(v[mid][1] <= suma)
        {
            if(v[mid][1] >= diferenta)
            {
                if(mid < prim) prim = mid;
                cautbin1(p, mid - 1);
            }
            else cautbin1(mid + 1, u);
        }
        else cautbin1(p, mid - 1);
    }

}

void cautbin2(int p, int u)
{
    if(p <= u)
    {
        int mid = (p + u) / 2;
        if(v[mid][1] <= suma)
        {
            if(v[mid][1] >= diferenta)
            {
                if(mid > last) last = mid;
            }
            cautbin2(mid + 1, u);
        }
        else cautbin2(p, mid - 1);
    }
}

int main()
{
    int  tot = 0;
    citire();
    sortare(1, n);
    for(int i = 1; i <= n - 2; ++i)
        for(int j = i + 1; j <= n - 1; ++j)
        {
            suma = v[i][1] + v[j][1];
            diferenta = abs(v[i][1] - v[j][1]);
            prim = 90100;
            last = -1;
            cautbin1(j + 1, n);
            cautbin2(j + 1, n);
            if(last != -1)
            {
                tot += (last - prim + 1);
            }
        }

    fout<<tot;
}