Cod sursa(job #2541348)

Utilizator Botzki17Botocan Cristian-Alexandru Botzki17 Data 8 februarie 2020 12:40:28
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("ntri.in");
ofstream fout("ntri.out");
const int NMAX = 800;
int v[NMAX+5];
///pentru aceasta problema folosim inegalitatea triunghiurilor c <= a + b, unde a, b, c sunt laturile triunghiului
int cautare_binara(int st, int dr, int i, int j)
{
    int mid, sol =0;
    while(st<=dr)
    {
        mid = (st + dr )>>1;
        if(v[mid]<=v[i] + v[j])
        {
            sol = mid;
            st = mid + 1;
        }
        else
            dr = mid-1;
    }
    if(sol == 0)
        return 0;
    return sol - j;
}

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