Cod sursa(job #1872849)

Utilizator ajajajEuuuuu ajajaj Data 8 februarie 2017 17:10:11
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
short k,i,result=-1,dif;
short N,a[801],x;
int nr;
int f(int start,int end,float k)
{
  int mid=(start+end)/2;
  if(start<=end)
{if(a[mid]>=k)
{
    result = mid;
return f(start,mid-1,k);
}
else
return f(mid+1,end,k);}
return result;
}
int g(int start,int end)
{
    int mid=(start+end)/2;
    if(start<=end)
    {
        if(a[mid]>=dif)
        {
            result=mid;
            return g(start,mid-1);
        }
        else
        return g(mid+1,end);
    }
    result=k-result;
    return result;   /// 13 28 89 364 468 473 480 648 736 785

}
void quick(int li,int ls)
{
int i,j,aux,m;
m=a[(li+ls)/2];
i=li; j=ls;
while(i<=j)
{
    while(a[i]<m && i<ls)
    i++;
    while(a[j]>m && j>li)
    j--;
    if(i<=j)
    {
        aux=a[i];
        a[i]=a[j];
        a[j]=aux;
        i++;
        j--;
    }
}
if(i<ls)
quick(i,ls);
if(j>li)
quick(li,j);
}
int main()
{
    fin>>N;
    for(i=1;i<=N;i++)
    fin>>a[i];
    quick(1,N);
    for(i=3;i<=N;i++)
    { x=f(2,i-1,a[i]/2.0);
        if(x!=-1)
        { for(k=x;k<=i-1;k++)
           {  result=k;
               dif=a[i]-a[k];
              nr+=g(1,k-1);
           }
        }
        result=-1;
    }
    fout<<nr;
    return 0;
}