Looksery Cup 2015 H. Degenerate Matrix

Looksery Cup 2015に参加しました。結果的にADHを通しました。レーティングは大幅に上がったのでハッピーです。

この問題は本番全く意味がわからないままサンプルを頼りにして通したんですが解法見て感動しました。

問題

Problem - 549H - Codeforces

解法

Bの行列式が0になるということは,

として,
とが平行であるということです。
一方で,
が意味することは,
として,
が頂点を中心とする一辺の長さがの内部にあり,が頂点を中心とする一辺の長さがの内部に存在するということです。

よって,の長さを二分探索しながら最適解を求めることが出来ます(二分探索回はやってないんですが多分atanの値が存在するかどうかでtrue or falseを分けるんですかね)。

ですが,実は二分探索をしなくても一発で答えを求めることが出来ます。よく考えると,最適解に対してとの関係としてありえるのは以下の4通りのみです。

(一つの正方形の右下ともう一方の正方形の左上を通る,etc)

これが意味することは,の行列の要素は

などとなるということです(他にもなどがあります)。

ということで,これらの場合にBの行列式が0になるのはどういう場合か考えてみます。例えばの場合を考えてみると,

となるので,となります。実際にはあり得る場合についてのような値を求め,その最大値でを割った値が答えになります。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a, b, c, d;
    cin >> a >> b;
    cin >> c >> d;
    if (a == 0 && b == 0 && c == 0 && d == 0) {
        cout << 0 << endl;
        return 0;
    }
    ll A[4]; A[0] = a; A[1] = b; A[2] = c; A[3] = d;
    ll p = 0;
    for (int i = 0; i < 16; i++) {
        int l = (i&1) ^ ((i>>3)&1);
        int r = ((i>>1)&1) ^ ((i>>2)&1);
        if (l != r) continue;
        ll tmp = 0;
        for (int j = 0; j < 4; j++) {
            if ((i>>j)&1) {
                tmp += -1*A[j];
            } else {
                tmp += A[j];
            }
        }
        p = max(p, abs(tmp));
    }
    if (p != 0) {
        double x = abs(1. * (a*d-b*c) / p);
        printf("%.15lf\n", x);
    } else {
        cout << 0 << endl;
    }
    return 0;
}