Cod sursa(job #989300)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 25 august 2013 14:31:35
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int Array[802],Result,N;
void Read()
{
    int i;
    f>>N;
    for(i=1;i<=N;i++)
        f>>Array[i];
    sort(Array+1,Array+N+1);
}
void Binary_Search1(int poz1,int poz2)
{
    int mid,st=1,dr=N,sol1=0,sol2=0;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(Array[mid]>Array[poz1]+Array[poz2])
        {
            dr=mid-1;
            continue;
        }
        if(Array[poz2]>Array[mid]+Array[poz1])
            st=mid+1;
        if(Array[poz2]<=Array[mid]+Array[poz1] && Array[poz2]+Array[poz1]>=Array[mid])
        {
            sol1=mid;
            st=mid+1;
        }
    }
    st=1;dr=N;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(Array[mid]>Array[poz1]+Array[poz2])
        {
            dr=mid-1;
            continue;
        }
        if(Array[poz2]>Array[mid]+Array[poz1])
            st=mid+1;
        if(Array[poz2]<=Array[mid]+Array[poz1] && Array[poz2]+Array[poz1]>=Array[mid])
        {
            sol2=mid;
            dr=mid-1;
        }
    }
    int counter=0;
    if(sol1==0 || sol2==0)
        return;
    if(sol2<=poz1)
        counter++;
    if(sol1>=poz2)
        counter++;
    Result+=sol1-sol2+1-counter;
}
void Binary_Search2(int poz1,int poz2)
{
    int mid,st=poz2+1,dr=N,sol1=0,sol2=1,used=0;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(Array[mid]>=Array[poz1]+Array[poz2])
        {
            dr=mid-1;
            continue;
        }
        if(Array[poz2]>=Array[mid]+Array[poz1])
            st=mid+1;
        if(Array[poz2]<Array[mid]+Array[poz1] && Array[poz2]+Array[poz1]>Array[mid])
        {
            sol1=mid;
            st=mid+1;
        }
    }
    st=poz2+1,dr=N;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(Array[mid]>=Array[poz1]+Array[poz2])
        {
            dr=mid-1;
            continue;
        }
        if(Array[poz2]>=Array[mid]+Array[poz1])
            st=mid+1;
        if(Array[poz2]<Array[mid]+Array[poz1] && Array[poz2]+Array[poz1]>Array[mid])
        {
            sol2=mid;
            dr=mid-1;
        }
    }
    if(sol1==0 || sol2==0)
        return;
    Result+=sol1-sol2+1;
}
void Browse()
{
    int i,j;
    for(i=1;i<=N;i++)
        for(j=i+1;j<=N;j++)
            Binary_Search1(i,j);
}
int main()
{
    Read();
    Browse();
    g<<Result/3<<"\n";
    return 0;
}