Pagini recente » Cod sursa (job #2620375) | Cod sursa (job #2711971) | Cod sursa (job #1185669) | Cod sursa (job #1858529) | Cod sursa (job #2105899)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n,v[805],capat1,capat2,inceput,nrtri,r1,r2;
int bincapat1(int x, int y){ //cea mai mica pozitie >= capat1
int lo = y, hi = n, mid, fina = 0;
while(lo <= hi){
mid = (lo + hi) / 2;
if(v[mid] < x){
lo = mid + 1;
}else{
fina = mid;
hi = mid - 1;
}
}
if(v[fina] >= capat1 && fina <= n){
return fina;
}else{
return 0;
}
}
int bincapat2(int x, int y){ //cea mai mare pozitie <= capat2
int lo = y, hi = n , mid ,fina = 0;
while(lo <= hi){
mid = (lo + hi) / 2;
if(v[mid] > x){
hi = mid - 1;
}else{
fina = mid;
lo = mid + 1;
}
}
if(v[fina] <= capat2){
return fina;
}else{
return 0;
}
}
int main(){
fin>>n;
for(int i = 1; i <= n; i++){
fin>>v[i];
}
sort(v + 1, v + 1 + n);
for(int i = 1; i < n; i++){
for(int j = i + 1; j <= n; j++){
inceput = max(i,j) + 1;
capat1 = abs(v[j] - v[i]);
capat2 = v[i] + v[j];
r1 = bincapat1(capat1, inceput);
r2 = bincapat2(capat2, inceput);
for(int p = r1; p <= r2; p++){
if(v[p] != 0){
nrtri++;
}
}
}
}
fout<<nrtri;
return 0;
}