POI 2 Stage 2 Triangles ( Ad hoc, Math, Fibonacci )

http://main.edu.pl/en/archive/oi/2/tro

題意：
給很多邊的長度，問是否可以構成三角形，可以的話輸出方案。

資料規模：
In the standard input there is a finite sequence of at least three positive integers not greater then 1e9, terminated by the number 0. Each number is written in a separate line. Positive numbers are lengths of line segments, and the number 0 denotes the end of the data.

解法：
把邊長排序後，檢查連續三個長度是否可以即可。原因是，小的邊希望最大的邊小，大的邊希望小的邊的總和盡量大。一個重要的優化是，不能構成三角形的例子是：[ 1, 1, 2, 3, 5, 8, 13, .. ]，而長度保證不超過 1e9，所以可以發現只要有超過 50 個邊，就一定有解。

時間 / 空間複雜度：
O( 50 lg 50 ) / O( 50 )

#include <bits/stdc++.h>
using namespace std;

signed main(){
  ios::sync_with_stdio( 0 );
  vector< int > side;
  for( int N; cin >> N and N; ){
    side.push_back( N );
    if( side.size() > 50 ) break;
  }
  sort( side.begin(), side.end() );
  for( int i = 0; i + 3 <= side.size(); ++i ){
    if( side[ i ] + side[ i + 1 ] > side[ i + 2 ] ){
      cout << side[ i ] << " " << side[ i + 1 ] << " " << side[ i + 2 ] << "\n";
      exit( 0 );
    }
  }
  cout << "NIE\n";
  return 0;
}