Pagini recente » Cod sursa (job #2863746) | Cod sursa (job #1284864) | Cod sursa (job #1687791) | Cod sursa (job #1861231) | Cod sursa (job #2061569)
#include<algorithm>
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
const int N = 800;
int v[N];
int n;
int indexOf(int x){
int left = 0;
int right = n-1;
while(left != right){
int middle = (left + right) / 2;
if(x <= v[middle])
right = middle;
else /// (x > v[middle])
left = middle+1;
}
return left;
}
int compare(int a, int b){ return a < b; }
int main()
{
int sol = 0;
in>>n;
for(int i=0; i<n; ++i)
in>>v[i];
sort(v, v+n, compare);
///for(int i=0; i<n; ++i) cout<<v[i]<<" "; cout<<"\n";
for(int firstIndex = 0; firstIndex < n; ++firstIndex)
for(int secondIndex = firstIndex + 1; secondIndex < n; ++secondIndex)
{
int thirdEdgeMaximalValue = v[firstIndex] + v[secondIndex];
int thirdIndex = indexOf(thirdEdgeMaximalValue);
while(thirdIndex < n-1 && v[thirdIndex+1] <= thirdEdgeMaximalValue)
++thirdIndex;
while(thirdIndex > 0 && v[thirdIndex] > thirdEdgeMaximalValue)
--thirdIndex;
int possibleEdgeLength = (thirdIndex - secondIndex);
if(possibleEdgeLength > 0)
{
sol += possibleEdgeLength;
///cout<<v[firstIndex]<<" "<<v[secondIndex]<<" --> index = "<<thirdIndex<<"\n";
}
}
out<<sol;
return 0;
}