Cod sursa(job #2035012)

Utilizator GiosinioGeorge Giosan Giosinio Data 8 octombrie 2017 20:27:28
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 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],unsigned short int i,unsigned short int j)
{
    bool oprire=0;
    unsigned short int m;
    while(i<j&&!oprire)
    {
        m=(i+j)/2;
        if(v[m]<=v[j]-v[i])
            i=m+1;
        else
            oprire=1;
    }
    if(i==j)
        return 0;
    return j-i-1;
}
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;
}