Pagini recente » Cod sursa (job #2896292) | Cod sursa (job #1943778) | Cod sursa (job #512742) | Cod sursa (job #2971059) | Cod sursa (job #2622993)
#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;
}