Cod sursa(job #2705556)

Utilizator octavi26octavian octavi26 Data 12 februarie 2021 19:59:13
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>
#define N 808

using namespace std;

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

int n;
int v[N];

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

int CautareBinara( int i, int j )
{
    int st, dr;
    int mij;
    int poz = -1;
    st = 1; dr = n;
    while( st <= dr )
    {
        mij = ( st + dr ) / 2;
        if( v[mij] <= v[i] + v[j] )
        {
            st = mij + 1;
            poz = mij;
        }
        else if( v[mij] > v[i] + v[j] )
        {
            dr = mij - 1;
        }
    }
    return poz;
}

inline bool triunghi( int a, int b, int c )
{
    if( a + b < c ) return 0;
    if( a + c < b ) return 0;
    if( c + b < a ) return 0;
    return 1;
}

void Rezolvare()
{
    int i, j;
    int x;
    int cb;
    int ct = 0;
    sort( v+1, v+n+1 );
    for( i=1; i<n; i++ )
        for( j=i+1; j<=n; j++ )
        {
            x = v[i] + v[j];
            cb = CautareBinara( i, j );
            //cout << i << " " << j << ": " << cb << " " << triunghi( v[i], v[j], v[cb] ) << "\n";
            if( triunghi( v[i], v[j], v[cb] ) ) ct += ( cb - j );
        }
    fout << ct;
}

int main()
{
    Citire();
    Rezolvare();
    fin.close();
    fout.close();
    return 0;
}