複数の数字から３つ選んで三角形になるかどうかを調べるとかいう話

とある本に書いてあったオマケ話。多分こう。

1. ソートして、大きい方からウインドウサイズ３で配列を見る。
2. 一番大きい辺が残りの２辺の和より大きければ三角形を作らない。そうじゃなければ終わり。
3. 一番大きい辺と比べて、次に大きい辺と次の次に大きい辺を取ってきたというのに、それを足しても一番大きい辺にはかなわないんだから、残りの奴らには太刀打ち出来ないだろう。なので諦めて次行ってみよう。

#include <cstdlib>

int cmp( const void *a, const void *b ){ return ( *( int* ) b - *( int* )a ); }
int page21_nlogn( int n, int *a ){
	qsort(a, n, sizeof(int), cmp);
	for( int i=0; i < n-2; ++i ){
		int s = a[i] + a[i+1] + a[i+2];
		if( s - 2 * a[i] > 0 )return s;
	}
	return 0;
}

これならO(n logn)
たのむからバブルソートはしないで。