Cod sursa(job #2612127)

Utilizator @dinescu.mateiDinescu Matei @dinescu.matei Data 8 mai 2020 15:19:48
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>
#include <fstream>

using namespace std;

ifstream f("nrtri.in");

ofstream g("nrtri.out");

void interschimbare( int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

int partition (int v[], int minim, int maxim)
{
    int pivot = v[maxim];
    int i = minim - 1;
    for(int j = minim; j<=maxim-1;j++)
    {
        if(v[j] < pivot)
        {
            i++;
            interschimbare(&v[i],&v[j]);
        }
    }
    interschimbare(&v[i+1],&v[maxim]);
    return (i+1);
}

void quicksort(int v[],int minim, int maxim)
{
    if (minim<maxim)
    {
        int pi = partition(v,minim,maxim);
        quicksort(v,minim,pi-1);
        quicksort(v,pi+1,maxim);
    }
}

int main()
{

    int n,v[800];
    f>>n;
    for(int i = 0;i < n;i++ )
        f>>v[i];
    quicksort(v,0,n-1);

    int nr = 0;

    for(int i=0;i<n-2;i++)
    {
        int k = i+2;
        for(int j=i+1;j<n;j++)
        {
            while(k<n && v[i] + v[j] >= v[k])
                k++;
            if (k>j)
                nr += k - j - 1;
        }
    }

    g<<nr;

    return 0;
}