Pagini recente » Cod sursa (job #2315908) | Cod sursa (job #3276921) | Cod sursa (job #2963697) | Cod sursa (job #2666456) | Cod sursa (job #3174527)
#include <bits/stdc++.h>
using namespace std;
FILE *fin, *fout;
const int NMAX = 800;
int v[NMAX];
int main() {
int n;
fin = fopen("nrtri.in", "r");
fscanf(fin, "%d", &n);
for(int i = 0; i < n; i++) {
fscanf(fin, "%d", &v[i]);
}
fclose(fin);
/*
* 3 betisoare formeaza un triunghi <=>
* a + b >= c, unde a <= b <= c
* => sortam betisoarele dupa lungime
* si fixam a si b si cautam binar c-ul maxim
* pentru care c <= a + b
* si vom adauga la raspuns numarul de numere
* dintre b si c, adica pozC - pozB
*/
sort(v, v + n);
int ans = 0;
for(int i = 0; i < n - 2; i++) {
for(int j = i + 1; j < n - 1; j++) {
int a = v[i], b = v[j];
int st = j + 1, dr = n; /// [st, dr)
while(dr - st > 1) {
int mij = (st + dr) / 2;
int c = v[mij];
if(c > a + b)
dr = mij;
else
st = mij;
}
if(v[st] <= a + b) {
ans += st - j;
}
}
}
fout = fopen("nrtri.out", "w");
fprintf(fout, "%d", ans);
fclose(fout);
return 0;
}