Pagini recente » Cod sursa (job #657950) | Cod sursa (job #1344638) | Cod sursa (job #2922216) | Cod sursa (job #361472) | Cod sursa (job #2839372)
#include<iostream>
#include<vector>
#include<fstream>
#include<algorithm>
// condition for a valid triangle: a + b > c
int _binary_search(const std::vector<int>& arr, int left, int right, int x, int y) {
int best = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
// std::cout << "Eu sunt mid: " << mid << "\n";
// std::cout << "Eu sunt left: " << left << " " <<
// "Eu sunt right: " << right << "\n";
if(arr[x] + arr[y] >= arr[mid]) {
best = mid;
left = mid + 1;
}
else {
right = mid - 1;
}
}
//in case we don't find any value return -1
// std::cout << "Eu sunt x: " << x << " Eu sunt y: " << y << "\n";
// std::cout << "Eu sunt best: " << best << "\n";
if(best <= y) {
return -1;
}
return best;
}
int main() {
int n; // nr bete
std::vector<int> values;
std::ifstream in("nrtri.in");
std::ofstream out("nrtri.out");
in >> n;
while(n--) {
int tmp;
in >> tmp;
values.push_back(tmp);
}
sort(values.begin(), values.end());
int res = -2;
// for(const auto& x: values)
// std::cout << x << " ";
// std::cout << "\n\n";
int counter = 0;
for(size_t i = 0 ; i < values.size() - 1; ++i) {
for(size_t j = i + 1; j < values.size(); ++j) {
res = _binary_search(values, 0, values.size() - 1, i, j);
if(res != -1) {
counter++;
// std::cout << i << " " << j << " " << res << "\n";
// out << i << " " << j << " " << res << "\n";
// std::cout << counter << "\n";
}
}
}
out << counter << "\n";
in.close();
out.close();
return 0;
}