Cod sursa(job #1291112)
Utilizator | Data | 12 decembrie 2014 11:57:15 | |
---|---|---|---|
Problema | Numarare triunghiuri | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.55 kb |
#include<fstream>
#include<algorithm>
using namespace std;
int n, i, j, p, u, sum, nr, mid;
int v[801];
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int main(){
fin>> n;
for(i = 1; i <= n; i++){
fin>> v[i];
}
sort(v + 1, v + n + 1);
for(i = 1; i < n - 1; i++){
for(j = i + 1; j < n; j++){
sum = v[i] + v[j];
p = j + 1;
u = n;
while(p <= u){
mid = (p + u) / 2;
if(v[mid] <= sum){
p = mid + 1;
}
else{
u = mid - 1;
}
}
nr += u - j;
}
}
fout<< nr;
return 0;
}