Cod sursa(job #2065688)

Utilizator nic_irinaChitu Irina nic_irina Data 14 noiembrie 2017 00:28:44
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <algorithm>
using namespace std;

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

int v[801];

int part_Hoare ( int s, int d )
{

    int i, j;
        i = s-1;
        j= d+1;
    int randpoz, r1, r2, r3;
    int nr = d-s+1;

    r1 = rand() % nr + s;
    r2 = rand() % nr + s;
    r3 = rand() % nr + s;

    int minr, maxr;
    minr = min ( min(r1, r2), min(r2, r3) );
    maxr = max ( max(r1, r2), max(r2, r3) );

    randpoz = r1+r2+r3 - minr-maxr;

    int pivot = v[randpoz];

    while (true){
        do
        {
            ++i;
        }while( v[i] < pivot);
        do
        {
            --j;
        }while( v[j] > pivot);
        if( i>=j )
            return j;
        swap(v[i], v[j]);
    }
}

void qsort (int i, int j)
{
    if(i<j){
        int k = part_Hoare( i, j );
        qsort(i, k);
        qsort(k+1, j);
    }
}

int caut_bin (int st, int dr, int x)
{
    int m = ( st + dr ) / 2;
    if( st >= dr )
    {
        if( v[m] <= x )
            return dr;
        else
            return st-1;
    }
    if( x < v[m] )
        return caut_bin( st, m-1, x );
    else
    //if( x >= v[m] )
        return caut_bin( m+1, dr, x );
}

int main()
{
    int n, i;
    fin>>n;
    for(i=1; i<=n; i++)
        fin>>v[i];
    qsort(1, n);
    int j, ind, k=0;
    for(i=1; i<= n-2; i++){
        for(j=i+1; j<=n-1; j++)
        {
            ind = caut_bin( j + 1, n, v[i]+v[j] );
            if( (v[i] +v[j]) >= v[ind] )
                k += (ind - j);
        }
    }
    fout<<k;

}