Pagini recente » Cod sursa (job #63862) | Cod sursa (job #345562) | Cod sursa (job #2419312) | Cod sursa (job #386201) | Cod sursa (job #789141)
Cod sursa(job #789141)
/*
* betisoare.cpp
*
* Created on: Sep 15, 2012
* Author: ab
*/
#include <fstream>
#include <algorithm>
#include <vector>
#define input "nrtri.in"
#define outputFile "nrtri.out"
#define MAX 30000
using namespace std;
int n;
vector<int> lungimi;
bool possible(int a, int b, int c){
return lungimi.at(c)<= lungimi.at(a) + lungimi.at(b) ;
}
int searchBete(int a, int b){
int pos = -1;
int start = b ;
int end = n -1;
while(start < end){
int mid = (start + end + 1)/2;
if(possible(a, b, mid))
start = mid ;
else
end = mid - 1;
}
if(possible(a, b, start))
pos = start;
return pos;
}
int main(){
int a, b,i, finalCount = 0;
ifstream in(input);
ofstream output;
output.open(outputFile);
in>>n;
for( i =0; i<n; i++){
in>>a;
lungimi.push_back(a);
}
sort(lungimi.begin(), lungimi.end());
for(a=0; a<n; a++ ){
for(b=a+1; b<n; b++){
int pos = searchBete(a, b);
if(pos != -1)
finalCount += pos - b ;
}
}
output << finalCount << endl;
output.close();
}