Cod sursa(job #1411872)

Utilizator mist.moonDenisa Gherghel mist.moon Data 31 martie 2015 23:38:14
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int a[810], n,nrtri;
void qsort(int a[810], int left, int right)
{
    int m=(left+right)/2, i=left, j=right,aux;
    int pivot=a[m];
    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(left<j) qsort(a, left, j);
    if(i<right) qsort(a,i,right);
}
int cautbin(int x, int p, int q)
{

    while(p<=q)
    {
        if(p==q) { if(a[p]<=x) return p; else return 0; }
        else {
            if(q-p==1) { if(x>=a[q]) return q; if(x>=a[p]) return p; }
            else {
                 int m=p+(q-p)/2;
        if(a[m]==x)
            if(a[m+1]!=x) return m;
            else p=m+1;
        else
            if(a[m]<x)
                if(a[m+1]>x) return m;
                else p=m+1;
            else
                if(a[m-1]<x) return m-1;
                else q=m-1;
            }
        }

    }

}
int main()
{
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    qsort(a,1,n);
    for(int i=1;i<n-1;i++)
    {
        int s=a[i]+a[i+1];
        int poz=cautbin(s,i+2,n);
        nrtri=nrtri+poz-i-1;
    }
    cout<<nrtri;
    return 0;
}