Cod sursa(job #61333)
Utilizator | Data | 18 mai 2007 21:04:34 | |
---|---|---|---|
Problema | Numarare triunghiuri | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.44 kb |
#include <cstdio>
#include <algorithm>
#define MAXN 800
using namespace std;
int n;
int V[MAXN];
int r;
int main( void )
{
freopen("nrtri.in", "r", stdin);
scanf("%d\n", &n);
int i;
for(i=0; i<n; ++i)
scanf("%d ", &V[i]);
sort(V, V+n);
int j;
int a, b, m, t;
for(i=0;i<=n-3;++i)
for(j=i+1;j<=n-2;++j)
{t=V[i]+V[j];
if(t>=V[j+1]) if(j==n-2) r++;
else if(t>=V[n-1]) r+=n-j-1;
else {
a=j+1; b=n-1;
while(a+1<b)
{
m=(a+b)/2;
if(t<V[m]) b=m;
else a=m;
}
r+=a-j;
}
}
freopen("nrtri.out", "w", stdout);
printf("%d\n", r);
return 0;
}