Cod sursa(job #502002)
Utilizator | Data | 17 noiembrie 2010 12:20:52 | |
---|---|---|---|
Problema | Numarare triunghiuri | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.46 kb |
#include<fstream>
using namespace std;
long long n,i,v[805],a,b,z,nrt,c,m;
int main(){
ifstream in("nrtri.in"); ofstream out("nrtri.out");
in>>n;
for(i=1;i<=n;i++){
in>>v[i];
}
sort(v+1,v+n+1);
for(a=1; a<=n-2; a++){
for(b=a+1; b<=n-1;b++){
c=b;m=n;
while (c<=m){
z=(c+m)/2;
if(v[z]<=(v[a]+v[b])){
c=z+1;
}
else {m=z-1;}
}
if(v[a]+v[b]>=v[z]){
nrt+=(z-b);
}
else{nrt+=(z-b-1);}
}
}
out<<nrt;
return 0;
}