2014 Yandex.Algorithm Elimination Stage, Round1 C - Non-Convex Quadrilaterals

問題文

問題概要

n 個の整数が与えられる．それらから4つ選んで，四角形の4辺の長さとする．
もちろん選び方によっては四角形が作れないが，そういう選び方は出来ないものとする．
こうしてできる四角形のうち，凹四角形であるもののなかで，周の長さが最も大きいものの値はなにか？

・制約
1 <= n <= 10^4
1 <= a_i <= 10^8

解法

実際に四角形を書けばすぐわかるが，ほとんどの四角形はいい感じに変形すると，
おなじ4辺をもつ凹四角形に変形できる．
したがって，基本的に四角形が作れるならそれは凹四角形にできるから，数字の大きい方から4つ選んでいって，実際に四角形を構築できるか考えれば十分である．
四角形が構築できる条件は，4つの辺のうちの最大の長さが他の3辺の長さの和未満であることである．

コーナーケースが1つあり，それは正方形である．これはどう変形しても凹四角形にできない．

計算量はソートの分で O(nlogn)．

ソースコード

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(rbegin(a), rend(a));
    int ans = -1;
    for(int i = 0; i + 3 < n; ++i) {
        if(a[i] == a[i + 1] && a[i] == a[i + 2] && a[i] == a[i + 3]) continue; // square
        int sum = 0;
        for(int j = i + 1; j <= i + 3; ++j) {
            sum += a[j];
        }
        if(sum > a[i]) {
            ans = a[i] + sum;
            break;
        }
    }
    cout << ans << endl;
}