Cod sursa(job #1838027)

Utilizator BLz0rDospra Cristian BLz0r Data 30 decembrie 2016 20:36:14
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<fstream>
#include<algorithm>
using namespace std;

#define NMAX 802

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

int v[NMAX];

int Bsearch(int x, int st, int dr) {

    int pozs = st - 1, pozd = st - 1;

    while (st <= dr) {
        int mid = st + ((dr - st) >> 1);

        if (v[mid] <= x) {
            pozd = mid;
            st = mid + 1;
        }
        else
            dr = mid - 1;
    }

    return pozd - pozs;
}

int main() {

    int N, Sol = 0;

    fin >> N;

    for (int i = 1; i <= N; ++i)
        fin >> v[i];

    sort(v + 1, v + N + 1); //sortam segementele dupa lungime


    //fixam 2 betisoare
    for (int i = 1; i <= N - 2; ++i)
        for (int j = i + 1; j <= N - 1; ++j)
            Sol += Bsearch(v[i] + v[j], j + 1, N); // cautam cel mai mare betisor <= suma celor 2 alese

    fout << Sol;

    return 0;
}