Cod sursa(job #1528129)

Utilizator CraiuAndrei Craiu Craiu Data 19 noiembrie 2015 08:29:25
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

int n, sol;
int a[805];

void Citire()
{
    int i;
    ifstream fin("nrtri.in");
    fin >> n;
    for(i = 1; i <= n; i++)
        fin >> a[i];
    sort(a + 1, a + 1 + n);
    fin.close();
}

int CautBin(int st, int dr, int x)
{
    int poz, mij;
    poz = 0;
    while( st <= dr)
    {
        mij = (st + dr) / 2;
        if(a[mij] > x)  dr = mij - 1;
        else{poz = mij; st = mij + 1;}
    }
    return poz;
}

void Rezolva()
{
    int i, j, p;
    for(i = 1; i <= n - 2; i++)
        for(j = i + 1; j < n; j++)
        {
            p = CautBin(j + 1, n, a[i] + a[j]);
            if(p != 0)  sol += (p - j);
        }
    ofstream fout("nrtri.out");
    fout << sol <<"\n";
    fout.close();
}

int main()
{
    Citire();
    Rezolva();
    return 0;
}