Cod sursa(job #1504721)

Utilizator refugiatBoni Daniel Stefan refugiat Data 18 octombrie 2015 09:01:43
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
const int NMAX=802;
int v[NMAX];
void sortare(int st,int dr)
{
    if(st==dr)
        return;
    int i=st,j=dr,aux,piv=(v[st]+v[dr])>>1;
    while(i<=j)
    {
        while(v[i]<piv) ++i;
        while(v[j]>piv) --j;
        if(i<=j)
        {
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
            ++i;
            --j;
        }
    }
    cout<<st<<' '<<dr<<'\n';
    sortare(st,(st+dr)>>1);
    sortare((st+dr)>>1+1,dr);

}
int main()
{
    ifstream si;
    si.open("nrtri.in");
    ofstream so;
    so.open("nrtri.out");
    int n;
    si>>n;
    int i;
    for(i=0;i<n;++i)
        si>>v[i];
    //sortare(0,n-1);
    sort(v,v+n);
    int j,val,st,dr,mij,poz,sum=0;
    for(i=0;i<n-2;++i)
    {
        for(j=i+1;j<n-1;++j)
        {
            val=v[i]+v[j];
            if(val>=v[j+1])
            {
                st=j+1;
                dr=n-1;
                poz=j+1;
                while(st<=dr)
                {
                    mij=(st+dr)>>1;
                    if(val>=v[mij])
                    {
                        poz=mij;
                        st=mij+1;
                    }
                    else
                    {
                        dr=mij-1;
                    }
                }
                //cout<<v[i]<<' '<<v[j]<<' '<<v[poz]<<'\n';
                sum+=poz-j;
            }
        }
    }
    so<<sum<<'\n';
    so.close();
    si.close();
    return 0;
}