Cod sursa(job #1717414)

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

using namespace std;
int k,i,j,n,nr,x;
long a[8001];
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;
    return ok;
}

int cautbin(int x,int y)
{
    int num=0;
    int i=0;
    int pas=1<<9;
    while(pas!=0)
    {
        if(i+pas<=n && a[i+pas]<=a[x]+a[y])
                i+=pas;
        pas/=2;
    }
    return i;
}

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(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
            {
                k=cautbin(i,j);
                if(k>j)
                {
                    nr+=k-j;
                    g<<a[i] << " " << a[j] << " " << a[k]<<endl;
                }
            }
    g<<nr;
    return 0;
}