Pagini recente » Cod sursa (job #349886) | Cod sursa (job #2924349) | Cod sursa (job #871805) | Cod sursa (job #730137) | Cod sursa (job #878038)
Cod sursa(job #878038)
#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;
}