Cod sursa(job #2510112)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 15 decembrie 2019 20:05:16
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <stdio.h>
#include <algorithm>
#define NMAX 800
using namespace std;

int n,v[NMAX+3];
FILE *fin,*fout;

int c_binar(int l1,int l2,int &tr)
{

    if(v[l1]+v[l2]>v[n])
    {
        tr+=n-l2;
        return n;
    }

    int st=l2;
    int dr=n;
    int rez=0;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(v[l1]+v[l2]<=v[mij])
        {
            //caut in stanga
            rez=mij;
            dr=mij-1;
        }
        else
        {
            //caut in dreapta
            st=mij+1;
        }
    }
    if(rez>0)
    {
        tr+=rez-l2-1;
    }
    return rez;
}

void afis()
{
    for(int i=1; i<=n; i++)
    {
        fprintf(fout,"%d ",v[i]);
    }
    fprintf(fout,"\n");
}

int main()
{
    fin=fopen("nrtri.in","r");
    fout=fopen("nrtri.out","w");

    fscanf(fin,"%d",&n);
    for(int i=1; i<=n; i++)
    {
        fscanf(fin,"%d",&v[i]);
    }
    sort(v+1,v+n+1);
    //afis();
    int triunghiuri=0;
    for(int i=1; i<=n-2; i++)
    {
        int ok=0;
        if(v[i]+v[i+1]<v[i+2])
        {
            break;
        }

        for(int j=i+1; j<=n-1; j++)
        {
            //fprintf(fout,"%d %d\n",v[i],v[j]);
            ok=c_binar(i,j,triunghiuri);
            //fprintf(fout,"%d\n",triunghiuri);
            if(ok==0)
            {
                break;
            }
        }
    }
    fprintf(fout,"%d",triunghiuri);
    return 0;
}