TopCoder SRM 764: RectangleHunt

問題概要

原文 → TopCoder Statistics - Problem Statement

個の点が与えられる。

与えられる点から 4 つ選んでできる長方形のうち、面積が最大のものを答えよ。ただし長方形を作ることができなければ -1 と答えよ。なお、長方形は軸に平行でなくてもよい。

解説

全探索が許される制約なので、4 重ループをしてそれぞれについて長方形になりうるかどうかを判定すればよい。

長方形を判定する前に、平行四辺形の場合にどのように判定するべきかを考える。以下、平行四辺形の頂点を反時計回りに とそれぞれおくことにする。おそらく最も簡単なのは以下の判定方法である。

• 辺 と辺 が平行
• 辺 と辺 が平行

しかし、これだけではまだ不十分な場合があって、たとえば一直線上に と並んでいるとき、上の条件をすべて満たしてしまう。なので、追加で以下の条件も見る必要がある。

• 辺 と辺 が平行でない

これらは全て外積の計算で判定できる。

では元の問題に立ち返り、長方形の場合にどうすべきか考える。長方形とは平行四辺形の特殊な例で、対角線の長さが等しくなる。つまり、下の条件も満たす必要がある。

• 辺 と辺 の長さが等しい

今回の問題とは関係ないが、正方形かどうかを判定するには 4 辺すべての辺の長さが等しい必要があるので追加で以下の条件も必要になるはず。(これが必要十分でなかったら教えてください)

• 辺 と辺 の長さが等しい

struct RectangleHunt {
    ll cross(pair<ll, ll> a1, pair<ll, ll> a2, pair<ll, ll> b1, pair<ll, ll> b2) {
        ll x1 = a1.first - a2.first;
        ll x2 = b1.first - b2.first;
        ll y1 = a1.second - a2.second;
        ll y2 = b1.second - b2.second;

        ll res = x1 * y2 - x2 * y1;
        return res;
    }

    ll area(pair<ll, ll> a1, pair<ll, ll> a2, pair<ll, ll> b1) {
        ll x1 = a1.first - b1.first;
        ll x2 = a2.first - b1.first;
        ll y1 = a1.second - b1.second;
        ll y2 = a2.second - b1.second;
        return llabs(x1 * y2 - y1 * x2);
    }

    ll len(pair<ll, ll> s1, pair<ll, ll> s2) {
        ll dfx = s1.first - s2.first;
        ll dfy = s1.second - s2.second;
        return dfx * dfx + dfy * dfy;
    }
    
    double get(const vector< pair<int, int> > &points, const vector<int> &ord) {
        vector< pair<int, int> > p;
        for(int i=0; i<4; i++) {
            p.emplace_back(points[ ord[i] ]);
        }

        if(cross(p[0], p[1], p[3], p[2]) != 0) return -1;
        if(cross(p[0], p[3], p[1], p[2]) != 0) return -1;
        if(cross(p[0], p[2], p[1], p[3]) == 0) return -1;
        if(len(p[0], p[2]) != len(p[1], p[3])) return -1;
        return area(p[0], p[1], p[3]);
    }
    
    double largest(vector <int> x, vector <int> y) {
        double ans = -1;
        int N = x.size();
        for(int i=0; i<N; i++) {
            for(int j=i+1; j<N; j++) {
                for(int k=j+1; k<N; k++) {
                    for(int l=k+1; l<N; l++) {
                        vector< pair<int, int> > points;
                        points.emplace_back(make_pair(x[i], y[i]));
                        points.emplace_back(make_pair(x[j], y[j]));
                        points.emplace_back(make_pair(x[k], y[k]));
                        points.emplace_back(make_pair(x[l], y[l]));

                        vector<int> ord(4);
                        iota(ord.begin(), ord.end(), 0);

                        do {
                            ans = max(ans, get(points, ord));
                        }while(next_permutation(ord.begin(), ord.end()));
                    }
                }
            }
        }
        return ans;
    }
};

幾何の条件いつもミスするけどそろそろどうにかしたいな。