Cod sursa(job #1264900)

Utilizator stanamd123Stana Marius Vlad stanamd123 Data 16 noiembrie 2014 14:26:19
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int N,V[805],i,j,rez,u,p,li,ls,m,B[30005],F[30005];

int caut1 (int p, int u, int sum)
{
    for (int i=p; i<=u; i++)
    {
        if (V[i]>=sum)
        {
            return i;
        }
    }
    return u;
}

int caut2 (int p, int u, int sum)
{
    int poz;
    for (int i=1; i<=u; i++)
    {
        if (V[i]<=sum)
        {
            poz=i;
        }
    }
    return poz;
}

int cautBin1 (int p, int u, int sum)
{
    li=p;
    ls=u;
    while (li<=ls)
    {
        m=(li+ls)/2;
        if (V[m]>=sum)
        {
            ls=m-1;
        }
        else
        {
            li=m+1;
        }
    }
    return li;
}

int cautBin2 (int p, int u, int sum)
{
    li=p;
    ls=u;
    while (li<=ls)
    {
        m=(li+ls)/2;
        if (V[m]<=sum)
        {
            li=m+1;
        }
        else
        {
            ls=m-1;
        }
    }
    return ls;
}

void preprocesare (void)
{
    for (i=1; i<=N; i++)
    {
        F[V[i]]++;
    }
    for (i=1; i<=30000; i++)
    {
        B[i]=B[i-1]+F[i];
    }
}

int cautSpec1(int dif)
{
    return B[dif-1]+1;
}

int cautSpec2(int sum)
{
    if (sum>30000)
    {
        return N;
    }
    else
    {
        return B[sum];
    }
}

int main()
{
    fin>>N;

    for (i=1; i<=N; i++)
    {
        fin>>V[i];
    }

    sort(V+1,V+N+1);
    preprocesare();

    for (i=1; i<=N-1; i++)
    {
        for (j=i+1; j<=N; j++)
        {
            u=cautSpec2(V[i]+V[j]);
            p=cautSpec1(V[j]-V[i]);
            rez += u - p + 1 - (i >= p && i <=u) - (j >= p && j <= u);
        }
    }

    fout<<rez/3;
    return 0;
}