Cod sursa(job #1212326)

Utilizator hopingsteamMatraguna Mihai-Alexandru hopingsteam Data 24 iulie 2014 13:55:42
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include    <iostream>
#include    <fstream>
#include    <algorithm>

using namespace std;

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

int a[805], n, sol;

int cautbin(int x, int lo, int hi,int j)
{
    while(lo <= hi)
    {
        int mid = (lo+hi)/2;
        if(x < a[mid]) hi = mid - 1;
        else
        {   if(x < a[mid + 1] || mid == n) return mid - j;
            else lo = mid + 1;
        }
    }
    return 0;
}

void read()
{
    fin>>n;
    for(int i = 1; i <= n; i++) fin >> a[i];
    sort(a+1, a+n+1);
    for(int i = 1; i <= n-2; i++)
    {
        for(int j = i+1; j <= n-1; j++)
        {
            sol+=cautbin(a[i]+a[j], j, n, j);
        }
    }
    fout<<sol<<"\n";
}

int main()
{
    read();
}