Cod sursa(job #2513712)

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

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

int caut_bin(int suma,int poz)
{
    int st=poz,dr=n;
    int solutie=n+1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(suma>=v[mij])
        {
            st=mij+1;
        }
        else if(suma<v[mij])
        {
            //caut in stanga
            solutie=mij;
            dr=mij-1;
        }
    }
    //fprintf(fout,"%d\n",solutie);
    return solutie-poz-1;
}

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]);
    }
    fclose(fin);

    sort(v+1,v+n+1);
   // afis();
    int grupe=0;
    for(int i=1; i<n-1; i++)
    {
        if(v[i]+v[i+1]<=v[n])
        {
            for(int j=i+1; j<=n-1; j++)
            {
                //fprintf(fout,"%d %d\n",i,j);
                grupe+=caut_bin(v[i]+v[j],j);
            }
        }
        else
        {
            grupe+=n-i-1;
        }
    }
    fprintf(fout,"%d",grupe);
    return 0;
}