Cod sursa(job #2063627)

Utilizator daniela12Sandu Daniela Teodora daniela12 Data 11 noiembrie 2017 12:22:35
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n, v[850], nr;
void citire ()
{
    int i;
    f>>n;
    for(i=1;i<=n;++i)   f>>v[i];
    f.close();
}
void cautabin(int x, int j)
{
    int li=j, ls=n ,mid, ok=0;
    while (li<=ls)
    {
        mid=li+(ls-li)/2;
        if(v[mid]<=x)  {ok=1; break;}
        else    ls=mid-1;
    }
    if(ok)
    {
        int m=mid;
        while(v[m]<=x && m>j)  m--, nr++;
        mid++;
        while(v[mid]<=x && mid<=n)  mid++, nr++;
    }
}
int hoare(int v[], int p, int r)
{
    int pivot = v[(p+r)/2];
    int i = p - 1, j = r + 1;
    while (true)
    {
        do
        {
            i++;
        } while (v[i] < pivot);
        do
        {
            j--;
        } while (v[j] > pivot);
        if (i >= j)
            return j;

        swap(v[i], v[j]);
    }
}

void quickSort(int v[], int p, int r)
{
    if (p < r)
    {
        int q = hoare(v, p, r);
        quickSort(v, p, q);
        quickSort(v, q + 1, r);
    }
}
int main()
{
    citire();
    quickSort(v, 1,n);
    int i, j;
    for(i=1;i<n;++i)
        for(j=i+1;j<=n;++j)
            cautabin (v[i]+v[j], j);
    g<<nr;
    g.close();
}