Cod sursa(job #1396789)
Utilizator | Data | 22 martie 2015 23:57:16 | |
---|---|---|---|
Problema | Numarare triunghiuri | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.85 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n,i,nr,j,a,e,hi,lo,mid,v[801],b,c,d,r,sum;
int mod(int f)
{
if(f<0)
f*=(-1);
return f;
}
int main()
{
fin >> n;
for(i = 1; i <= n; ++i)
fin >> v[i];
sort(v+1,v+n+1);
for(i = 1; i <= n;++i)
for(j = i + 1; j <= n; ++j)
{
a = mod(v[i]-v[j]);
b = v[j]+v[i];
hi = n;
lo = 1;
while(lo<hi)
{
mid = lo + (hi-lo)/2;
if(v[mid]<a)
lo = mid+1;
else if(v[mid]>a)
hi = mid-1;
else {while(v[mid-1]==a)
--mid;
break;}
}
while((v[mid]>a)&&(mid>1))
--mid;
if(v[mid]<a)
++mid;
d = mid;
hi = n;
lo = 1;
while(lo<hi)
{
mid = lo + (hi-lo)/2;
if(v[mid]<b)
lo = mid+1;
else if(v[mid]>b)
hi = mid-1;
else {while(v[mid+1]==b)
++mid;
break;}
}
while((v[mid]<b)&&(mid<n))
++mid;
if(v[mid]>b)
--mid;
e = mid;
if(e-d-1>0)
nr+=e-d-1;
}
fout << nr/2;
return 0;
}