Cod sursa(job #1161330)

Utilizator BologaDragosBologa Dragos BologaDragos Data 31 martie 2014 10:23:54
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("nrtri.in") ;
ofstream g("nrtri.out") ;

int v[801],n ;

int cautare(int k,int p)
{
    int mij,u=n ;
    while(p<u)
    {
        mij=p+(u-p)/2 ;
        if(v[mij]<k)
            p=mij+1 ;
        else
            u=mij ;
    }
        if(v[mij]<k)
            mij++ ;
        if(v[mij]<k)
            return -1 ;
        return mij ;


}


int main()
{
    int ct=0,i,j,k,p,u,t ;
    f>>n ;
    for(i=1;i<=n;i++)
        f>>v[i] ;
    sort(v+1,v+n+1) ;
    for(i=1;i<=n-2;i++)
        for(j=i+1;j<=n-1;j++)
        {
           p=v[j]-v[i] ;
           t=j+1 ;
           k=cautare(p,t) ;
           if(k==j)
            k++ ;
           for(t=k;t<=n;t++)
                if(v[i]+v[j]>=v[t])
                {
                    ct++ ;
                    g<<v[i]<<" "<<v[j]<<" "<<v[t]<<"\n" ;
                }
                else
                    break ;
        }
    g<<ct ;
    return 0;
}