Cod sursa(job #472522)

Utilizator miculprogramatorA Cosmina - vechi miculprogramator Data 25 iulie 2010 15:02:34
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

int v[801];
int n, i, j, k;
int total_tr;

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

int main ()
{
    FILE *f = fopen ("nrtri.in","r");
    FILE *g = fopen ("nrtri.out","w");
    fscanf (f,"%d", &n);
    for (i=1; i<=n; ++i)
        fscanf (f,"%d", &v[i]);

    sort (v + 1, v + 1 + n);

    for (i=1; i<=n; ++i)
        for (j=i+1; j<=n; ++j)
        {
            //printf ("%d\n", cautare());
            total_tr += (cautare() - j);
        }

    fprintf (g, "%d", total_tr);

    fclose (g);
    fclose (f);
    return 0;
}