Cod sursa(job #1701611)

Utilizator Esteban_AlexCihodaru Ciprian-Alexandru Esteban_Alex Data 13 mai 2016 17:48:00
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;

int n,a[810];

void Citire()
{
    freopen("nrtri.in","r",stdin);

    scanf("%d",&n);

    int i;

    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
}

void Aux(int &x,int &y)
{
    int aux;

    aux=x;
    x=y;
    y=aux;
}

int Partitionare(int st,int dr)
{
    int p,piv,i,j;

    p=rand()%(dr-st+1)+st;

    Aux(a[p],a[st]);

    piv=a[st];
    i=st+1;
    j=dr;

    while(i<=j)
    {
        if(a[i]<=piv) i++;
        if(a[j]>piv) j--;
        if((i<j) && (a[i]>piv) && (a[j]<=piv))
        {
            Aux(a[i],a[j]);
            i++;
            j--;
        }
    }

    a[st]=a[i-1];
    a[i-1]=piv;
    return i-1;
}

void QS(int st,int dr)
{
    int p;

    p=Partitionare(st,dr);

    if(st<p-1)     QS(st,p-1);
    if(p+1<dr)      QS(p+1,dr);
}

int Sol()
{
    int i,j,k=0,nrtri=0;

      for(i=1;i<=n;i++)
        {
            k=i+2;
            for(j=i+1;j<=n;j++)
            {
                while(k<=n && a[i]+a[j]>=a[k]) k++;
                if(j+1<=k+1) nrtri+=k-j-1;
            }
        }

    return nrtri;
}
int main()
{
    Citire();
    QS(1,n);

    freopen("nrtri.out","w",stdout);
    printf("%d\n",Sol());
    return 0;
}