Cod sursa(job #481086)

Utilizator CossAlbulescu Cosmina Coss Data 30 august 2010 15:21:04
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

int v[1000];
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)
            total_tr += (cautare() - j);

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

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