Pagini recente » Autentificare | Istoria paginii runda/preoni11/clasament | Istoria paginii runda/simulare_oji_10_2 | Monitorul de evaluare | Cod sursa (job #1969997)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n;
vector <short> bat;
int triunghiuri;
short regula1(short i,short j){
short left=i,right=j,mid;
while(left<=right){
mid=(left+right)/2;
if(bat[mid]<bat[j]-bat[i]){
left=mid+1;
}
else if(bat[mid]>=bat[j]-bat[i]){
right=mid-1;
}
}
return left;
}
short regula2(short i,short j){
short left=i,right=j,mid;
while(left<=right){
mid=(left+right)/2;
if(bat[mid]>bat[j]+bat[i])
right=mid-1;
else left=mid+1;
}
return right;
}
short caut(short i,short j){
return regula2(i,j)-regula1(i,j);
}
int main(){
f>>n;
for(short i=1,lungime;i<=n;i++)
f>>lungime,bat.push_back(lungime);
sort(bat.begin(),bat.end());
for(short i=0;i<n-3;i++){
for(short j=n-1;j>=i+2;j--)
triunghiuri+=caut(i,j);
}
g<<triunghiuri;
f.close();
g.close();
}