Cod sursa(job #2063589)

Utilizator daniela12Sandu Daniela Teodora daniela12 Data 11 noiembrie 2017 12:12:27
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
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();
}
int compara (const void *a, const void *b)
{
    if(*(int *)a<*(int *)b) return -1;
    if(*(int *)a==*(int *)b)    return 0;
    return 1;
}
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 main()
{
    citire();
    qsort(v, n, sizeof(int), compara);
    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();
}