Mai intai trebuie sa te autentifici.
Cod sursa(job #1085960)
Utilizator | Data | 17 ianuarie 2014 16:28:42 | |
---|---|---|---|
Problema | Numarare triunghiuri | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.22 kb |
#include <cstdio>
#include <algorithm>
using namespace std;
int N,v[1000];
inline int BSearch1(int x)
{
int st,dr,mij;
st=1; dr=N;
while(st<=dr)
{
mij=(st+dr)/2;
if(v[mij]<=x)
st=mij+1;
else
dr=mij-1;
}
mij=(st+dr)/2;
if(v[mij]>x)
--mij;
return mij;
}
inline int BSearch2(int x)
{
int st,dr,mij;
st=1; dr=N;
while(st<=dr)
{
mij=(st+dr)/2;
if(v[mij]>=x)
dr=mij-1;
else
st=mij+1;
}
mij=(st+dr)/2;
if(v[mij]<x)
++mij;
return mij;
}
int main()
{
int i,j,k,sol=0,poz1,poz2;
freopen ("nrtri.in","r",stdin);
freopen ("nrtri.out","w",stdout);
scanf("%d", &N);
for(i=1;i<=N;++i)
scanf("%d", &v[i]);
sort(v+1,v+N+1);
for(i=1;i<N;++i)
for(j=i+1;j<=N;++j)
{
poz1=BSearch1(v[i]+v[j]);
poz2=BSearch2(max(v[i]-v[j],v[j]-v[i]));
sol+=(poz1-poz2+1);
if(poz2<=i && i<=poz1)
--sol;
if(poz2<=j && j<=poz1)
--sol;
}
sol/=3;
printf("%d\n", sol);
return 0;
}