Pagini recente » Cod sursa (job #1261597) | Borderou de evaluare (job #565552) | Cod sursa (job #2588311) | Rating Vlad Alexandru Toader (shibuya) | Cod sursa (job #2075180)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int stixlen;
int stix[841];
int binSearch(int n, int lg)
{
int pos = 0;
for(; lg > 0; lg >>= 1){
if(pos + lg <= stixlen){
if(stix[pos + lg] <= n){
pos += lg;
}
}
}
return pos;
}
int invBinSearch(int n, int lg)
{
int pos = stixlen;
for(; lg > 0; lg >>= 1){
if(pos - lg > 0){
if(stix[pos - lg] >= n){
pos -= lg;
}
}
}
return pos;
}
int findValidTriangles(int first, int last, int lg)
{
int smallest = stix[last] - stix[first];
int biggest = stix[first] + stix[last];
int r = binSearch(biggest, lg) - invBinSearch(smallest, lg) + 1;
if(smallest <= stix[first]){
r--;
}
if(biggest >= stix[last]){
r--;
}
if(r > 0){
cout << stix[first] << " " << stix[last] << "\n";
}
return max(r, 0);
}
int main()
{
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int validTriangles = 0, lg;
fin >> stixlen;
for(lg = 1; lg <= stixlen; lg <<= 1);
for(int i = 1; i <= stixlen; i++){
fin >> stix[i];
}
sort(stix + 1, stix + stixlen + 1);
//cout << invBinSearch(1, lg) << " " << binSearch(5, lg);
/*
for(int i = 1; i <= stixlen; i++){
cout << stix[i] << " ";
}
*/
for(int i = 1; i <= stixlen; i++){
for(int j = i + 1; j <= stixlen; j++){
//cout << findValidTriangles(i, j, lg) << " ";
validTriangles += findValidTriangles(i, j, lg);
}
}
fout << validTriangles / 3;
return 0;
}