Mai intai trebuie sa te autentifici.
Cod sursa(job #2616535)
Utilizator | Data | 18 mai 2020 20:02:59 | |
---|---|---|---|
Problema | Numarare triunghiuri | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.15 kb |
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
short getBound(short target, short v[], short size, bool up) {
if (target >= v[size - 1]) return size - 1;
if (target <= v[0]) return 0;
short max = size - 1, pivot = size/2, min = 0;
while (pivot != min && pivot != max) {
if (target == v[pivot]) return pivot;
if (target > v[pivot]) min = pivot;
else max = pivot;
pivot = (max + min) / 2;
}
if (up) return max;
else return min;
}
int main()
{
fstream f("nrtri.in", ios::in);
short n;
f >> n;
short* b = new short[n];
for (int i = 0; i < n; i++) f >> b[i];
f.close();
f.open("nrtri.out", ios::out);
sort(b, b + n);
int total = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
short up = getBound(b[i] + b[j], b, n, false), down = getBound(abs(b[i] - b[j]), b, n, true);
total += up - down + 1;
if (i <= up && i >= down) total--;
if (j <= up && j >= down) total--;
for (int k = down; k <= up; k++) {
if(k != i && k != j) f << i << " " << j << " " << k << "\n";
}
}
}
f << total / 6;
f.close();
}