Cod sursa(job #1587953)

Utilizator RazvanatorHilea Razvan Razvanator Data 2 februarie 2016 18:12:47
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <iostream>

using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int v[801],n,sum;

void QuickSort(int left,int right,int v[800])
{
    int poz=v[(left+right)/2];
    int i=left,j=right,man;
    while (i<=j) {
        while (v[i]<poz) i++;
        while (v[j]>poz) j--;
        if (i<=j) {
            man=v[i];
            v[i]=v[j];
            v[j]=man;
            i++;
            j--;
        }
    }
    if (i<right) QuickSort(i,right,v);
    if (left<j) QuickSort(left,j,v);
}

int caut_bin(int a,int b,int n)
{
    int pas=1<<10,i=0,s=0;
    while (pas!=0) {
        if (a+b>=v[n+i+pas+1] && i+pas<=n) {s=s+i;i+=pas;cout<<a<<" "<<b<<" "<<v[n+i+pas]<<'\n';}
        pas/=2;
    }
    return s;
}

int main()
{
    fin>>n;
    for (int i=1;i<=n;i++) fin>>v[i];
    QuickSort(1,n,v);
    for (int i=1;i<=n;i++) {
        for (int j=i+1;j<=n;j++) {
            sum+=caut_bin(v[i],v[j],i);
        }
    }
    fout<<sum;
}