Cod sursa(job #1659716)
| Utilizator | Data | 22 martie 2016 15:20:36 | |
|---|---|---|---|
| Problema | Numarare triunghiuri | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.59 kb |
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int N, v[1000];
int main()
{
in >> N;
for (int i = 1; i <= N; ++i)
in >> v[i];
int i, j, l, r,piv,mid;
int nr = 0;
sort(v + 1, v + N + 1);
for (i = 1; i <= N - 2; ++i)
{
piv = i + 2;
for (j = i + 1; j <= N - 1; ++j)
{
l = piv, r = N;
while (l <= r)
{
mid = (l + r) >> 1;
if (v[i] + v[j] < v[mid])
r = mid - 1;
else
l = mid + 1;
}
nr += r - j,piv=r;
}
}
out << nr;
return 0;
}