Cod sursa(job #2778809)

Utilizator ililogIlinca ililog Data 2 octombrie 2021 11:10:07
Problema Numarare triunghiuri Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
using namespace std;
#include<bits/stdc++.h>

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n, nrtri;
int v[801];

int cautbin(int i, int j) {
    
    int st = 1, dr = n;
    int x = 0;
    
    while (st <= dr) {
        int mid = (st+dr)/2;
        if (v[mid] > v[i]+v[j]) {
            dr = mid-1;
        } else {
            x = mid;
            st = mid+1;
        }
    }
    
    if (x <= j) {
        return 0;
    }
    
    return x-j;
}

int main() {
    
    fin >> n;
    for (int i = 1; i<=n; i++) {
        fin >> v[i];
    }
    
    sort(v+1, v+n+1);
    
    for (int i = 1; i<=n-2; i++) {
        for (int j = i+1; j<=n-1; j++) {
            cout << v[i] << " " << v[j] << " " << cautbin(i,j) << endl;
            nrtri = nrtri + cautbin(i,j);
        }
    }
    
    fout << nrtri;
    
    return 0;
}