Cod sursa(job #1948357)

Utilizator andreiutu111Noroc Andrei Mihail andreiutu111 Data 31 martie 2017 23:53:02
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <algorithm>

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

int N,x[801],l1,l2,l3,st,dr;
long l;

int main()
{
    fin>>N;
    for(int i=1;i<=N;i++)
        fin>>x[i];

    sort(x+1,x+N+1);


    for(int i=1;i<=N-2;i++){
        l1=x[i];
        for(int j=i+1;j<N;j++){
            l2=x[j];

            st=j+1,dr=N;
            if(st==dr){

                if(l1+x[st]>=l2 && l2+x[st]>=l1 && l1+l2>=x[st])l++;

            }else{

                short q=1;
                while(st<dr && q){
                    int mij=(st+dr)/2;

                    if(l1+x[mij]>=l2 && l2+x[mij]>=l1 && l1+l2>=x[mij])l++,q=0;
                    else if(l1+x[mij]<l2 || l2+x[mij]<l1)st=mij+1;
                    else if(l1+l2<x[mij])dr=mij-1;

                }

            }

        }

    }

    fout<<l;
}