Pagini recente » Cod sursa (job #3000220) | Cod sursa (job #3202127) | Cod sursa (job #1969873) | Cod sursa (job #3265823) | Cod sursa (job #2769266)
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n,v[805],ans;
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i];
sort(v+1,v+n+1); //pointer+intreg e ok, dar intreg+pointer nu e ok O(n log n) sortarea din STL
/**
Daca laturile triunghiului sunt v[i]<v[j]<v[k] atunci v[i]+v[j]>=v[k], i<j<k
**/
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
int st=j+1;
int dr=n;
int sol=-1;
while(st<=dr)
{
int mid=(st+dr)/2;
if(v[mid]<=v[i]+v[j])
{
sol=mid;
st=mid+1;
}
else dr=mid-1;
}
if(sol!=-1)
ans+=sol-j; //[j+1,sol]
}
fout<<ans<<'\n';
return 0;
}