Cod sursa(job #2038166)

Utilizator GiosinioGeorge Giosan Giosinio Data 13 octombrie 2017 13:48:54
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream f("nrtri.in");
ofstream g("nrtri.out");

bool cmp(unsigned short int a, unsigned short int b)
{
    return a<=b;
}
void sortare(unsigned short int n,unsigned short int v[800])
{
    sort(v+0,v+n,cmp);
}

unsigned short int ctbin (unsigned short int v[800],short int i,short int j)
{
    unsigned short int m,nr_tri=0;
    unsigned short int ind_i=i,ind_j=j;
    ind_i++;ind_j--;
    while(ind_i<=ind_j)
    {
        m=(ind_i+ind_j)/2;
        if(v[m]<=v[j]-v[i])
            ind_i=m+1;
        else
        {
            nr_tri=nr_tri+ind_j-m+1;
            ind_j=m-1;
        }
    }
    return nr_tri;
}
int main()
{
    unsigned short int n,i,j,nr;
    f>>n;
    unsigned short int v[n];
    for(i=0;i<n;i++)
    {
        f>>v[i];
    }
    sortare(n,v);
    for(i=nr=0;i<n-2;i++)
        for(j=i+2;j<n;j++)
            nr=nr+ctbin(v,i,j);
    g<<nr;
}