Cod sursa(job #514530)

Utilizator ariel_roAriel Chelsau ariel_ro Data 18 decembrie 2010 22:13:26
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
/* qsort example */
#include <stdio.h>
#include <stdlib.h>

#define NX 805

int N, a[NX];
FILE *in = fopen("nrtri.in", "r");
FILE *out = fopen("nrtri.out", "w");

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

void cit()
{
    fscanf(in, "%d", &N);
    for (int i = 0; i < N; i++)
        fscanf(in, "%d", &a[i]);
}

int main ()
{
  cit();
  qsort (a, N, sizeof(int), compare);

  if (N < 3)
  {
      fprintf(out, "%d", 0);
      return 0;
  }

  int l1 = 0, l2 = 0, l3 = 0, nrtri = 0;
  for (int i = 0; i < N - 2; i++)
  {
     l1 = a[i];
     for (int j = i + 1; j < N - 1; j++)
     {
        l2 = a[j];
        int p = j + 1, u = N - 1, m = 0, tri = 0;
        while (p <= u)
        {
            m = (p + u) >> 1;
            if (a[m] <= l1 + l2)
            {
                tri = m;
                p = m + 1;
            }
            else
                u = m - 1;
        }

        nrtri += (tri > j) ? (tri - j) : 0;
     }
  }

  fprintf(out, "%d", nrtri);
  return 0;
}