Pagini recente » Cod sursa (job #2117761) | Cod sursa (job #1015235) | Cod sursa (job #2447345) | Cod sursa (job #2062631) | Cod sursa (job #2075154)
#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);
if(smallest < stix[first]){
r--;
}
if(biggest > stix[last]){
r--;
}
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);
/*
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;
return 0;
}