Cod sursa(job #2622993)

Utilizator miramaria27Stroie Mira miramaria27 Data 2 iunie 2020 13:44:11
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <iostream>
#include <fstream>
using namespace std;
void interclasare(int a[], int i, int j,int m)
{

    int aux[i+j-1];
    int p=i;
    int q=m+1;
    int k=0;
    while(p<=m && q<=j)
    {
        if(a[p]<a[q])
            aux[k++]=a[p++];
        else
            aux[k++]=a[q++];
    }
    while(p<=m)
        aux[k++]=a[p++];
    while(q<=j)
        aux[k++]=a[q++];

    for(int l=i; l<=j; l++)
        a[l]=aux[l-i];

}

void mergesort(int a[],int i,int j)
{
    if(i<j)
    {
        int m=(i+j)/2;
        mergesort(a,i,m);
        mergesort(a,m+1,j);
        interclasare(a,i,j,m);
    }
}
int nrTriunghiuri(int a[], int N)
{

    int i=0;
    int j=i+1;
    int nr=0;
    while(i<N-2) ///consideram elementul de pe poz i ca fiind prima latura a,
                 ///este evident ca nu o sa parcurgem cu i vectorul pana la sfarsit
                 ///(trebuie in vector sa avem si elementele b si c)
    {

        int k=j+1;
        ///conditia ca a,b,c sa fie laturi ale unui triunghi este
        ///ca a+b>c
        ///iterand prin lista ordonata,vom cauta cel mai mare c pentru care conditia ete satisfacuta
        ///evident, toate numerele mai mici decat acest c gasit vor respecta de asemenea conditia->
        /// o sa pot sa formeze triunghiuri cu elementele de pe poz i si j
        while(k<N && a[i]+a[j]>=a[k])k++;
        if(j)nr+=k-j-1;

        j++;
        if(j==N)
        {
           ///am terminat de verificat elementul i cu latura de pe pozitia j, j+1,....
           /// iteram la urmatorul element care sa fie prima latura a triunghiului
           /// atentie: trebuie sa schimbam si j-ul in functie de noul i
           i++;
           j=i+1;
        }

    }
    return nr;

}
int main()
{
    ifstream in("nrtri.in");
    ofstream out("nrtri.out");
    int a[801];
    int N;
    in>>N;
    for(int i=0;i<N;i++)
        in>>a[i];
     mergesort(a,0,N-1);
    out<<nrTriunghiuri(a,N);
    return 0;
}