Pagini recente » Cod sursa (job #609201) | Cod sursa (job #1652855) | Cod sursa (job #2708155) | Cod sursa (job #2116977) | Cod sursa (job #989276)
Cod sursa(job #989276)
#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=poz1+1,dr=poz2-1,sol1=0,sol2=1;
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=poz1+1,dr=poz2-1;
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;
}
}
Result+=sol1-sol2+1;
}
void Binary_Search2(int poz1,int poz2)
{
int mid,st=poz2+1,dr=N,sol1=0,sol2=1;
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;
}
}
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);
Binary_Search2(i,j);
}
}
int main()
{
Read();
Browse();
g<<Result<<"\n";
return 0;
}