C++で45度の直線により平面を重みの合計が等しい2つの領域に分割できるか判定する方法

問題概要

2次元平面上に n 個の異なる点 (Xi, Yi) が与えられ、それぞれの点には重み Wi が設定されています。このとき、直線の両側に存在する点の重みの合計が等しくなるような45度の直線を引けるかどうかを判定してください。

たとえば、入力が {{-1,1,3},{-2,1,1},{1,-1,4}} の場合、出力は TRUE となります。

アプローチ：座標変換と累積和

傾き45度の直線は、一般に「x − y = c(cは任意の定数)」という式で表せます。そこで各点を u = x − y という1つの値に変換すると、問題は「数直線上に配置された重みを、ある位置で2つのグループに分け、それぞれの重みの合計を一致させられるか」という1次元の問題に置き換えられます。

この変換により、あとは u 座標ごとに重みを集計して累積和を作り、すべての分割位置を順番に調べるだけで答えが求まります。直線が点と点の間を通るケースと、いくつかの点がちょうど線上に乗る(線上の点はどちら側にも含まれない)ケースの2通りをチェックするのがポイントです。

アルゴリズムの手順

• n をベクトル v のサイズとします。
• u 座標ごとの重みを保持するマップ weight_at_x を定義します。
• max_x を -2000、min_x を 2000 で初期化します。
• i = 0 から n - 1 まで繰り返します。
  • temp_x = v[0][i] - v[1][i](点の u 座標)を求めます。
  • max_x と min_x を更新します。
  • weight_at_x[temp_x] に v[2][i](重み)を加算します。
• 累積和を格納する配列 sum_temp を定義し、先頭に 0 を挿入します。
• x = min_x から max_x まで、sum_temp の末尾に「直前の累積値 + weight_at_x[x]」を追加していきます。
• total_sum を sum_temp の最後の要素(全重みの合計)とします。
• partition_possible を false で初期化し、i = 1 から sum_temp のサイズ未満まで以下を確認します。
  • sum_temp[i] == total_sum - sum_temp[i] ならば、partition_possible を true にします(直線が隣接する座標の間を通る場合)。
  • sum_temp[i - 1] == total_sum - sum_temp[i] ならば、partition_possible を true にします(u 座標が min_x + i - 1 の点がすべて直線上に乗る形で分割できる場合)。
• 最後に partition_possible を返します。

C++実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void is_valid_part(vector<vector<int>> &v){
    int n = v.size();
    map<int, int> weight_at_x;
    int max_x = -2000, min_x = 2000;
    for (int i = 0; i < n; i++) {
        int temp_x = v[0][i] - v[1][i];
        max_x = max(max_x, temp_x);
        min_x = min(min_x, temp_x);
        weight_at_x[temp_x] += v[2][i];
    }
    vector<int> sum_temp;
    sum_temp.push_back(0);
    for (int x = min_x; x <= max_x; x++) {
        sum_temp.push_back(sum_temp.back() + weight_at_x[x]);
    }
    int total_sum = sum_temp.back();
    int partition_possible = false;
    for (int i = 1; i < sum_temp.size(); i++) {
        if (sum_temp[i] == total_sum - sum_temp[i])
            partition_possible = true;
        if (sum_temp[i - 1] == total_sum - sum_temp[i])
            partition_possible = true;
    }
    printf(partition_possible ? "TRUE" : "FALSE");
}
int main() {
    vector<vector<int>> v = {{-1,1,3},{-2,1,1},{1,-1,4}};
    is_valid_part(v);
}

入力

{{-1,1,3},{-2,1,1},{1,-1,4}}

出力

TRUE

動作例

入力 {{-1,1,3},{-2,1,1},{1,-1,4}} の場合、各点の u = x − y の値はそれぞれ -2、-3、2 となり、重みの合計は 8 です。累積和を計算すると途中で 4(全体の半分)になる位置が存在するため、45度の直線で均等に分割可能であることがわかり、結果は TRUE になります。

計算量

座標の範囲を R(max_x − min_x)とすると、累積和の構築と走査に O(n + R) 時間が必要です。マップの操作を含めると全体で O(n log n + R) 程度となり、点の数に対して十分高速に動作します。