Cod sursa(job #1161290)

Utilizator BologaDragosBologa Dragos BologaDragos Data 31 martie 2014 10:04:44
Problema Numarare triunghiuri Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 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 ;
    f>>n ;
    for(i=1;i<=n;i++)
        f>>v[i] ;
    sort(v+1,v+n+1) ;
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
        {
            p=v[j]-v[i] ;
            u=v[i]+v[j] ;
            k=cautare(p,j) ;
            while(k==i||k==j)
                k++ ;
            if(k!=-1)
            while(v[k]<u&&k<=n)
            {
                if(k!=i&&k!=j&&v[k]!=0)
                {
                    ct++ ;
                    //g<<v[i]<<" "<<v[j]<<" "<<v[k]<<"\n" ;
                }
                k++ ;
            }
        }
    g<<ct ;
    return 0;
}