Pagini recente » Cod sursa (job #2243081) | Borderou de evaluare (job #559871) | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #1753022) | Cod sursa (job #456922)
Cod sursa(job #456922)
#include<fstream>
using namespace std;
#define nmax 802
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n,v[nmax],x1,x2;
void citire()
{
f>>n;int i;
for(i=1;i<=n;i++) f>>v[i];
}
void swap(int &i,int &j)
{
int aux=i;i=j;j=aux;
}
void DownHeap( int from, int to )
{
for( int son=2*from; son < to; from=son, son=2*from )
{
if( son < to-1 && v[son+1] > v[son] )
++son;
if( v[from] >= v[son] )
return;
swap( v[from], v[son] );
}
}
void HeapSort( int from, int to )
{
int i;
for( i=(to-from)/2; i > 0; --i )
DownHeap( i, to );
while( to > from )
{
swap( v[from], v[to-1] );
--to;
DownHeap( from, to );
}
}
int search_left(int st)
{
int dr=n,mij;
while(st<dr)
{
mij=(st+dr)/2;
if(v[mij]>=x2)dr=mij;
else st=mij+1;
}
if(v[st]>=x2&&v[st]<=x1)return st-1;
return 0;
}
int search_right(int st)
{
int dr=n,mij;
while(st<dr)
{
mij=(st+dr)/2+1;
if(v[mij]<=x1)st=mij;
else dr=mij-1;
}
if(v[dr]<=x1&&v[dr]>=x2)return dr;
return 0;
}
int main()
{
citire();HeapSort(1,n+1);
int i,j,nr=0;
for(i=1;i<n-1;i++)
for(j=i+1;j<n;j++)
{
x1=v[i]+v[j];x2=v[j]-v[i];
nr+=search_right(j+1)-search_left(j+1);
}
g<<nr<<'\n';
}