Cod sursa(job #642463)

Utilizator idomiralinIdomir Alin idomiralin Data 1 decembrie 2011 13:54:38
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
# include <cstdio>
# include <algorithm>

using namespace std;

int  contor, ct, val, n, a[805];
int cautbin(int st, int dr, int i, int j)
{int mij;
    
    while (st <= dr)
    {
          mij = (st + dr) / 2;
          if ((a[i] + a[j] >= a[mij] && a[i] + a[j] < a[mij + 1]) || (a[i] + a[j] >= a[mij] && mij == n))
          return mij;
          if (a[i] + a[j] < a[mij]) dr = mij - 1;
                               else st = mij + 1;
          }                     

}

int i, j, k;
int main()
{
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    
    scanf("%d",&n);
    for (i = 1; i <= n; i++)
    scanf("%d",&a[i]);
    
    sort(a + 1, a + n + 1);
 
    for (i = 1; i < n - 1; i++)
        for (j = i + 1; j < n; j++)
        {
            val = cautbin(1, n, i, j);
            if (val) contor += val - j;
            }
 
 
    /*for (i = 1; i <= n; i++)
        for (j = i + 1; j <= n; j++)
            for (k = j + 1; k <= n; k++)
            if ((a[i] > 0 && a[j] > 0 && a[k] > 0) && 
            (a[i] + a[j] >= a[k]) && (a[i] + a[k] >= a[j]) &&
            (a[j] + a[k] >= a[i])) ct++;
                              else break;
     */
           
    printf("%d",contor);

return 0;
}