Cod sursa(job #1364976)

Utilizator andreeaanbrusAndreea Anbrus andreeaanbrus Data 27 februarie 2015 22:31:11
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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


int n, v[805], cnt;

int cautare(int st, int dr, int caut)
{
    int mij;
    while(st <= dr)
    {
        mij = (st + dr)/2;
        if(v[mij] <= caut)
            st = mij + 1;
        else
            if(v[mij] > caut )
                dr = mij - 1;
    }
    while ( caut < v[mij] )
        mij--;
    return mij;
}
int main()
{
    fin>>n;
    for(int i = 1; i <= n; i++)
        fin>>v[i];
    sort(v + 1, v + n + 1);

    for(int i = 1; i <= n - 2 ; i++)
        for(int j = i + 1; j <= n - 1; j++)
        {
            int vc = cautare(j + 1 , n , v[i]+v[j]);
            cnt += vc - j;

        }
    fout<<cnt;

return 0;
}