Cod sursa(job #2624912)

Utilizator marian222200Dimofte Marian marian222200 Data 5 iunie 2020 16:31:14
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
// tema_sd_mare.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <fstream>
#include <algorithm>
#define N 800
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int v[N];
int n;
int cautare_binara(int s, int d, int i, int j){
    int m, nr = 0;
    while (s <= d){
        m = (s + d) / 2;
        if (v[m] <= v[i] + v[j]){
            nr = m;
            s = m + 1;
        }
        else
            d = m - 1;
    }
    if (nr == 0)
        return 0;
    return nr - j;///numarul de muchii posibile de cuplat cu v[i] si v[j]
}
void citire() {
    fin >> n;
    for (int i = 0; i < n; i++)
        fin >> v[i];
}
int rez() {
    int i, j, s = 0;
    for (i = 0; i < n; i++){
        for (j = i + 1; j < n; j++){
            s = s + cautare_binara(j + 1, n-1, i, j);
        }
    }
    return s;

}
int main(){
    citire();
    sort(v, v + n);
    fout << rez();
    return 0;
}
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file