Cod sursa(job #1132153)

Utilizator FawkesAndrei Colhon Fawkes Data 2 martie 2014 19:20:53
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
int a[850];
int main()
{
    ifstream f("nrtri.in");
    ofstream g("nrtri.out");
    int n,k=0,cm;
    f >> n;
    for(int i=1;i<=n;++i)
    {
        f >> a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n-1;++i)
    {
        for(int j=i+1;j<=n;++j)
        {
            int st,dr,mid;
            st=j+1;
            dr=n;

            while(st<=dr)
            {
                mid=(st+dr)/2;
                cm=mid;
                if(a[mid]<=a[i]+a[j])
                {
                    ++k;
                    if(a[cm+1]<=a[i]+a[j])
                    {
                        while(a[cm+1]<=a[i]+a[j]&&cm+1<=n)
                        {
                            ++k;
                            cm=cm+1;
                        }

                    }
                    if(a[mid-1]<=a[i]+a[j])
                    {
                        while(a[mid-1]<=a[i]+a[j]&&mid-1>j)
                        {
                            ++k;
                            mid=mid-1;
                        }

                    }
                    break;
                }
                if(a[mid]<a[i]+a[j]) st=mid+1;
                if(a[mid]>a[i]+a[j]) dr=mid-1;
            }

        }
    }
    g << k;
    return 0;
}