Cod sursa(job #914624)

Utilizator GManiakGhenea Catalin GManiak Data 14 martie 2013 12:19:22
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int v[801],n,nr;
void schimb(int i,int j)
{
    int aux;
    aux=v[i];
    v[i]=v[j];
    v[j]=aux;
}
void sort(int l,int h)
{
    int piv,i=l,j=h;
    piv=(l+h)/2;
    piv=v[piv];
    while(i<=j)
    {
        while(v[i]<piv)
            i++;
        while(v[j]>piv)
            j--;
        if(i<=j)
            schimb(i++,j--);
    }
    if(i<h)
        sort(i,h);
    if(j>l)
        sort(l,j);
}
int caut(int x)
{
    int i=0,pas=1<<9;
    while(pas!=0)
    {
        if(i+pas<=n && v[i+pas]<x)
            i+=pas;
        pas/=2;
    }
    return i;
}
void solve()
{
    int x,y,z,d;
    for(x=n;x>2;x--)
    {
        for(y=x-1;y>1;y--)
        {
            z=v[x]-v[y];
            if(z<=v[y])
                 nr+=(y-caut(z)-1);
            else
                break;

        }
    }
}
int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i];
    sort(1,n);
    solve();
    out<<nr;
    return 0;
}