Cod sursa(job #878038)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 13 februarie 2013 19:59:34
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 kb
#include <fstream>
#include <algorithm>

using namespace std;

int main()
{
    //Deschidere fisierelor de intrare si iesire
    ifstream fin("nrtri.in");
    ofstream fout("nrtri.out");

    //Vectorul si numarul sau de elemente
    int v[810];
    int n;

    //Citim numarul de elemente ale vectorului
    fin>>n;

    //Citim vectorul folosind contorul i
    int i;

    for(i=0;i<n;i++)
        fin>>v[i];

    //Sortam vectorul crescator
    sort(v,v+n);

    //Un alt contor - j
    int j;

    //Suma, respectiv diferenta dintre betele curente
    int sum,dif;

    //Variabilele cautarii binare
    int cap,coada,mijl;

    //Minimul si maximul ce vor fi gasite de catre cautarile binare ce urmeaza
    int minim,maxim;

    //Numarul de triunghiuri
    int triunghiuri=0;

    //Se aleg doua bete diferite
    for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
        {
            //Se calculeaza diferenta dintre ungimea lor
            dif=v[j]-v[i];

            //Din inegalitatea triunghiului rezulta ca trebuie sa gasim cel mai scurt bat din vector
            //cu proprietatea ca este cel putin egal cu dif, putem face acest lucru prin cautare binara, retinand
            //doar pozitia pe care acesta apare
            cap=j+1;
            coada=n-1;
            mijl=(n+j)/2;
            minim=n;

            while(cap<=coada)
            {
                if(v[mijl]>=dif)
                {
                    if(mijl<minim)
                    {
                        minim=mijl;
                    }

                    coada=mijl-1;
                }
                else
                {
                    cap=mijl+1;
                }

                mijl=(cap+coada)/2;
            }


            //Trebuie, de asemenea, sa gasim cel mai lung bat din vector cu proprietatea ca este cel mult egal
            //in lungime cu suma dintre v[i] si v[j] (adica sum). Putem face acest lucru printr-o cautare binara
            cap=j+1;
            coada=n-1;
            mijl=(n+j)/2;
            maxim=-1;
            sum=v[i]+v[j];

            while(cap<=coada)
            {
                if(v[mijl]<=sum)
                {
                    if(mijl>maxim)
                    {
                        maxim=mijl;
                    }

                    cap=mijl+1;
                }
                else
                {
                    coada=mijl-1;
                }

                mijl=(cap+coada)/2;
            }

            //Numarul de triunghiuri creste cu succesorul diferentei dintre pozitiile maxim si minim
            if(maxim-minim+1>0)
                triunghiuri+=(maxim-minim+1);
        }

    //Se afiseaza raspunsul
    fout<<triunghiuri<<'\n';


    //Inchiderea fisierelor de intrare si iesire
    fin.close();
    fout.close();
    return 0;
}