1

2次元グラフにN個の点があるとします。各点には重みが付いています。線が点を2つのグループに分割し、総重量（の重量の合計）になるように直線を描く必要があります。そのグループ内のポイント）重量の小さいパーツをできるだけ多くします。私の仕事はこの値を見つけることです。どうすればよいですか？

注：3つのポイントが同じ線上にあることはありません。

これは宿題でもコンテストの一部でもありません。

4

1 に答える 1

2

最適なソリューションが見つかるまで、すべての角度とオフセットをスキャンするだけです。

計算を簡単にするために、単純な回転行列を使用してすべてのポイントを回転させ、ポイントをスキャンラインに合わせます。これにより、x 座標のみを確認するだけで済みます。

スキャンラインが倍増する前に半円をチェックするだけで済みます。これは、度ではなくラジアンで作業していると仮定すると、PI に対して 0 の角度です。また、x、y、および重みの値を持つある種のオブジェクトとしてデータからポイントを読み取ることができると仮定します。

擬似コード:

Initialize points from input data
Initialize bestDifference to sum(weights of points)
Initialize bestAngle to 0
Initialize bestOffset to 0
Initialize angleStepSize to an arbitrary small value (e.g. PI/100)

For angle = 0:angleStepSize:PI
    Initialize rotatedpoints from points and rotationMatrix(angle)

    For offset = (lowest x in rotatedpoints) to (highest x in rotatedpoints)
        weightsLeft = sum of the weights of all nodes with x < offset
        weightsRight = sum of the weights of all nodes with x > offset
        difference = abs(weightsLeft - weightsRight)
        If difference < bestDifference 
            bestAngle = angle
            bestOffset = offset
            bestDifference = difference

    Increment angle by stepsize
Return bestAngle, bestOffset, bestDifference

私のアプローチを明確にするための粗いペイント画像を次に示します。

2Dグラフ画像

于 2012-09-18T00:53:31.203 に答える