Cod sursa(job #2577965)

Utilizator vladiordac2004Vlad Iorda vladiordac2004 Data 10 martie 2020 10:51:56
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <fstream>
///nrtri de pe infoarena(merge si L1+L2=L3)
using namespace std;
ifstream f("nrtri.in");ofstream g("nrtri.out");
int n,v[801],x=0;

void citire()
{
    int i;
    f>>n;
    for (i=1;i<=n;i++)
        f>>v[i];
}

void quicksort(int p,int q)
{
    int i,j,m,aux;
    m=(p+q)/2;
    i=p;
    j=q;
    while (i<j)
    {
        while (i<q&&v[i]<v[m])
            i++;
        while (p<j&&v[m]<v[j])
            j--;
        if (i<=j)
        {
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
            i++;
            j--;
        }
        if (i<q)
            quicksort(i,q);
        if (p<j)
            quicksort(p,j);
    }
}

int cautbin(int lo,int hi,int l)
{
    int mid,ok=0;
    while (ok==0&&hi-lo>=1)
    {
        mid=(hi+lo)/2;
        if (v[mid]==l)
            return mid;
        else if (v[mid]>l)
            return (mid+1,hi,l);
        else
            return (lo,mid-1,l);
    }
}



void rezolvare()
{
    int i,j,l;
    for (i=1;i<=n-2;i++)
        for (j=i+1;j<=n-1;j++)
        {
            l=v[j]+v[i];
            x=x+j-cautbin(i,j,l)+1;
        }
    g<<x;
}

int main()
{
    citire();
    quicksort(1,n);
    rezolvare();
    return 0;
}