Cod sursa(job #2311939)

Utilizator mirceatlxhaha haha mirceatlx Data 3 ianuarie 2019 21:16:16
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int v[805],i,n,j;
int nrtri=0;
void Citire()
{
    fin>>n;
    for(i=1; i<=n; i++)
        fin>>v[i];
}

int Cautare(int sum,int i)
{
    bool ok=false;
    int poz=-1;
    int Left=i+1;
    int Right=n;
    int Mid;
    while(Left<=Right)
    {
        Mid=(Left+Right)/2;
        if(sum>=v[Mid])
        {
            ok=true;
            poz=Mid-i;
        }
        if(ok)
        {
             Left=Mid+1;
             ok=false;
        }
        else
        {
            if(sum<v[Mid])
                Right=Mid-1;
            if(sum>v[Mid])
                Left=Mid+1;
        }
    }
    if(poz==-1)
        return 0;
    else
        return poz;
}

int main()
{
    int suma=0;
    Citire();
    sort(v+1,v+n+1);
    if(n==1)
    {
        fout<<0;
        return 0;
    }
    if(n==2)
    {
        fout<<0;
        return 0;
    }
    for(i=1; i<n; i++)
        for(j=i+1; j<=n; j++)
        {
                suma=suma+Cautare(v[i]+v[j],j);
        }
    fout<<suma;
    return 0;
}