Cod sursa(job #1411895)

Utilizator mist.moonDenisa Gherghel mist.moon Data 31 martie 2015 23:59:01
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <stdio.h>
using namespace std;
int a[810], n,nrtri,s,j,poz;
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 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-2;i++)
        for(int j=i+1; j<=n-1;j++)
        {
            int s=a[i]+a[j]; poz=n;
            while(a[poz]>s and poz>j) poz--;
            if(poz!=j) nrtri=nrtri+poz-j;
        }

    printf("%d \n", nrtri);
    return 0;
}