Pagini recente » Cod sursa (job #2397903) | Cod sursa (job #644102) | Cod sursa (job #2117723) | Cod sursa (job #3196168) | Cod sursa (job #3141274)
/*
Fie laturile unui triunghi: a, b, c
! Realtia unui Triunghi: a + b > c
*/
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
#define INFILE "nrtri.in"
#define OUTFILE "nrtri.out"
#define VMAX 801
ifstream fin (INFILE);
ofstream fout (OUTFILE);
int n;
int aux, v[VMAX];
void afisare(){
for(int i = 1; i <= n; ++i){
fout << v[i] << " ";
}
fout << '\n';
}
bool triunghi(int a, int b, int c){
return (a + b >= c) &&
(b + c >= a) &&
(c + a >= b);
}
int upper_bound(int valoare){
int st = 1, dr = n;
while(st < dr){
int mij = (st + dr + 1) / 2;
if(v[mij] <= valoare){
st = mij;
}
else{
dr = mij - 1;
}
}
return st;
}
void rezolvare(){
int sum = 0, indice, cnt = 0, indice_aux;
for(int i = 1; i < n; ++i){
for(int j = i + 1; j <= n; ++j){
sum = v[i] + v[j];
indice = upper_bound(v[j]);
while(!triunghi(v[i], v[j], v[indice])){
--indice;
}
indice_aux = indice;
while(triunghi(v[i], v[j], v[indice_aux])){
if(indice_aux == i || indice_aux == j){
--cnt;
}
else{
// fout << "a: " << v[i] << "; b: " << v[j] << "; c: " << v[indice_aux] << '\n';
}
--indice_aux;
}
cnt += (indice - indice_aux);
}
}
fout << cnt / 2 << '\n';
}
void read(){
fin >> n;
for(int i = 1; i <= n; ++i){
fin >> v[i];
}
// afisare();
sort(v + 1, v + n + 1);
// afisare();
rezolvare();
}
int main(){
read();
return 0;
}