問題へのリンク

問題概要

N 個の値 a_1, a_2, ..., a_N が与えられる。このうちの 3 つをうまく選ぶことで、3 辺の長さがそれらになるような三角形を作ることができるかどうか判定せよ。

制約

3 <= N <= 20000

解法

三角形の成立条件は a < b < c に対して、c < a+b で与えられる。

素朴に考えると O(N³) の探索をすることになるが、O(NlogN) でできる。まずはソートしておく。そして c を決めうちする。

c の値を仮定すると、a < b < c なる a, b のうち a+b が最も大きくなるものが c を超えるかどうかを判定すればよい。そのような a, b は c 以下のうち大きい順に 2 つとればよい。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<long long> val;

int main() {
    while (cin >> N) {
        val.resize(N);
        for (int i = 0; i < N; ++i) cin >> val[i];
        sort(val.begin(), val.end());
        bool ok = false;
        for (int i = 0; i < N-2; ++i) {
            if (val[i + 2] < val[i] + val[i+1]) ok = true;
        }
        if (ok) cout << "possible" << endl;
        else cout << "impossible" << endl;
    }
}