Cod sursa(job #1567311)

Utilizator daneel95Holteiu Daniel-Ninel daneel95 Data 13 ianuarie 2016 08:58:40
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<fstream>
#include<algorithm>

using namespace std;

ifstream in("nrtri.in");
ofstream out("nrtri.out");

int n;
int a[805];

void quickSort(int a[], int l, int r) {
      int i = l, j = r;
      int aux;
      int pivot = a[(l + r) / 2];

      while (i <= j) {
            while (a[i] < pivot)
                  i++;
            while (a[j] > pivot)
                  j--;
            if (i<= j) {
                  aux = a[i];
                  a[i] = a[j];
                  a[j] = aux;
                  i++;
                  j--;
            }
      }

      if (l < j)
            quickSort(a, l, j);
      if (i < r)
            quickSort(a, i, r);
}

int main()
{
    int i,j,st,dr,m;
    int nr=0;
    in>>n;
    for(i=1;i<=n;i++)
        in>>a[i];

    quickSort(a,1,n);

    for(i=1;i<=n-1;i++)
        for(j=i+1;j<=n;j++)
        {
            st=j;
            dr=n+1;
            while(st+1<dr)
            {
                m=(st+dr)/2;
                if(a[m]<=a[i]+a[j]) st=m;
                    else dr=m;
            }
                nr=nr+st-j;
        }
    out<<nr;
    in.close();
    out.close();
    return 0;
}