Cod sursa(job #2495831)

Utilizator MirunaStefaniaLupascu Miruna-Stefania MirunaStefania Data 19 noiembrie 2019 21:14:08
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include<fstream>
#include<cstring>
#define N 805
#include<algorithm>
using namespace std;

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

int n,a[N];

void read()
{
    int i;
    fin>>n;
    for(i=1;i<=n;++i)
        fin>>a[i];
}

bool cauta(int s,int d,int sum,int dif)
{
    int m;
    while(s<d)
    {
        m=(s+d)/2;
        if(a[m]>sum)s=m+1;
        else if(a[m]<dif)d=m-1;
                else break;     ///asa gasim doar unul
    }
    if(a[m]<=sum&&a[m]>=dif)return 1;
    else return 0;
}

void solve()
{
    sort(a+1,a+n+1);
    int i,j,ct=0,sum,dif;
    //alegem 2 betisoare, il cautam si pe al 3 lea in mod convenabil
    //suma oricaror 2 mai mare decat al 3 lea
    //dif oricaror 2 mai mica decat a 3a
    for(i=1;i<=n-2;++i)
        for(j=i+1;j<=n-1;++j)
    {
        sum=a[i]+a[j];dif=a[j]-a[i];
        if(cauta(j+1,n,sum,dif))ct++;
        //cout<<i<<" "<<j<<" "<<(cauta(j+1,n,sum,dif))<< "\n";

    }
    fout<<ct;
}


int main()
{
    read();
    solve();

    return 0;
}