Pagini recente » Cod sursa (job #699169) | Istoria paginii runda/porc/clasament | Cod sursa (job #2646612) | Statistici Hangan Florin (hanganflorin) | Cod sursa (job #1415269)
#include <iostream>
#include <fstream>
#include <list>
int a[800];
void radixSort(int *v, int size)
{
static const int BASE = 10;
std::list<int> bucket[BASE];
for ( int n = 1; n < 30000; n *= BASE )
{
int k = 0;
for ( int i = 0; i < size; ++i )
{
bucket[(v[i]/n)%BASE].push_back(v[i]);
}
for ( int i = 0; i < BASE; bucket[i++].clear() )
{
for ( std::list<int>::iterator j = bucket[i].begin(); j != bucket[i].end(); ++j )
{
v[k++] = (*j);
}
}
}
}
int isTriangle( int x, int y, int z )
{
if ( x+y >= z && x+z >= y && y+z >= x )
{
return 1;
}
return 0;
}
int bsearch( int st, int dr, int val1, int val2 )
{
while ( st <= dr )
{
int m = ( st + dr ) / 2;
if ( isTriangle( val1, val2, a[m] ) )
{
st = m + 1;
}
else
{
dr = m - 1;
}
}
return st;
}
int counttri( int *v, int size )
{
int count = 0;
for ( int i = 0; i < size - 2; ++i )
{
for ( int j = i+1; j < size - 1; ++j )
{
int poz = bsearch( j+1, size, v[i], v[j] );
count += poz - j - 1;
}
}
return count;
}
int main( int argc, char* argv[] )
{
std::ifstream input("nrtri.in");
std::ofstream output("nrtri.out");
int N;
input >> N;
for ( int i = 0; i < N; ++i )
{
input >> a[i];
}
radixSort( a, N );
output << counttri( a, N ) << "\n";
input.close();
output.close();
return 0;
}