Cod sursa(job #1526511)

Utilizator ManDark97Melinte Tudor-Matei ManDark97 Data 16 noiembrie 2015 20:07:53
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int v[801],n,i,j,s;
/*void qs(int st,int dr)
{
    int i=st,j=dr;
    int pivot=v[(st+dr)/2];
    while(i<=j)
    {
        while(v[i]<pivot)i++;
        while(v[j]>pivot)j--;
        if(i<=j)
            v[i]=v[i]+v[j]-(v[j]=v[i]),i++,j--;
    }
    if(st<j)
        qs(st,j);
    if(i<dr)
        qs(i,dr);
}*/
int cautarebinara(int p,int q)
{
    int st=p,dr=q,k=0,mij;
    while(st<=dr && st<=q && dr>=p)
    {
        mij=(st+dr)/2;
        if(v[mij]<=v[i]+v[j] && dr-st==0)
        {return k;}
        if(v[mij+1]<=v[i]+v[j])
            k++,dr=mij-1;
        else
           st=mij+1;
    }
    return k;
}
int main()
{
    in>>n;
    for(i=1;i<=n;i++)
        in>>v[i];
    sort(v+1,v+n+1);
   // qs(1,n);
    for(i=1;i<=n;i++)cout<<v[i]<<" ";    cout<<endl;
    for(i=1;i<n-1;i++)
        for(j=i+1;j<n;j++)
        s+=cautarebinara(j+1,n);
    out<<s;

    return 0;
}