Cod sursa(job #1839631)

Utilizator IsacLucianIsac Lucian IsacLucian Data 3 ianuarie 2017 11:26:18
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>
#define nmax 805
using namespace std;
int a[nmax],n;
int CautareBinare(int capat,int x)
{
    int st=capat,dr=n,mij,poz=0;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]<=x)
        {
          st=mij+1;
          poz=mij;
        }
        else dr=mij-1;
    }
    return poz;
}
int main()
{
    ifstream fin("nrtri.in");
    ofstream fout("nrtri.out");
    int i,j,sol=0,y,x,st;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    sort(a+1,a+n+1);
    for(i=1;i<n-1;i++)
     for(j=i+1;j<n;j++)
    {
        x=a[i]+a[j];
        st=j+1;
        y=CautareBinare(st,x);
        if(y!=0)
            sol+=y-st+1;                          ///am gasit solutie de la j+1.......y
    }
    fout<<sol<<"\n";
    fin.close();
    fout.close();
    return 0;
}