Cod sursa(job #1717383)

Utilizator raresm44vasile rares raresm44 Data 14 iunie 2016 19:27:17
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>

using namespace std;
int k,i,j,n,a[100],nr,x;

void quick(int inf, int sup) {
  int x, i, j, t;
  i = inf;
  j = sup;
  x = a[(i + j) / 2];
  do {
    while ( (i < sup) && (a[i] < x) ) i++;
    while ( (j > inf) &&(a[j] > x) ) j--;
    if ( i<= j ) {
      t = a[i];
      a[i] = a[j];
      a[j] = t;
      i++;
      j--;
    }
  } while ( i <= j );
  if ( inf < j ) quick(inf, j);
  if ( i < sup ) quick(i, sup);
}

bool tri(int x,int y,int z)
{
    int ok=1;
    if(a[x]+a[y]<a[z])
        ok=0;
    if(a[x]+a[z]<a[y])
        ok=0;
    if(a[z]+a[y]<a[x])
        ok=0;
    if(x==y)
        ok=0;
    if(y==z)
        ok=0;
    if(z==x)
        ok=0;
    return ok;
}

int cautbin(int x)
{
    int i=0;
    int pas=1<<9;
    while(pas!=0)
    {
        if(i+pas<=n && tri(k,j,i+pas))
            i+=pas;
        pas/=2;
    }
    return i-1;
}
int main()
{
    ifstream f("nrtri.in");
    ofstream g("nrtri.out");
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
    quick(1,n);
    for(k=1;k<=n;k++)
        for(j=k+1;j<=n;j++)
            nr+=cautbin(x);
    g<<nr;
    return 0;
}