Cod sursa(job #1536246)

Utilizator AlexVolatiluVoicu Alex AlexVolatilu Data 25 noiembrie 2015 21:20:44
Problema Numarare triunghiuri Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>

using namespace std;

int n,v[801],aux[801],poz,k;

void interclasare(int st, int dr, int m)
{
    int i=st,j=m+1,k=st;
    while(i<=m&&j<=dr)
    {
        aux[k++] = v[i]<v[j] ? v[i++] : v[j++];
    }
    while(i<=m) aux[k++]=v[i++];
    while(j<=dr) aux[k++]=v[j++];
    for(k=st;k<=dr;k++)
        v[k]=aux[k];
}

void mergesort(int st, int dr)
{
    if(st==dr) return;
    int m=(st+dr)/2;
    mergesort(st,m);
    mergesort(m+1,dr);
    interclasare(st,dr,m);
}

void cautbin(int st, int dr)
{
    if(st>dr) return;
    int m=(st+dr)/2;
    poz=m;
    if(k>v[m]) cautbin(m+1,dr);
    else if(k<v[m]) cautbin(st,m-1);
    else return;
}

int main()
{
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    int a,b,i,j,n1,n2,nr=0;
    scanf("%d",&n);
    n1=n-1;n2=n-2;
    for(i=0;i<n;i++)
        scanf("%d",v+i);

    mergesort(0,n-1);

    for(a=0;a<n2;a++)
        for(b=a+1;b<n1;b++)
        {
            k=v[a]+v[b];
            cautbin(b+1,n-1);
            if(v[poz]>k) poz--;
            nr+=poz-b;
        }

    printf("%d",nr);
    return 0;
}