【C++】線分の中心を移動させて実現できる最大の交差領域を求める方法

はじめに

このチュートリアルでは、線分の中心を移動させることで実現できる最大の交差領域を求めるC++プログラムについて解説します。

この問題では、3つの線分の中心座標とそれぞれの長さが与えられます。各線分の中心は距離Kまで移動することが許されており、その移動を活用して交差領域の長さを最大化することが目的です。

アルゴリズムの考え方

まず、3つの中心座標を昇順にソートし、最も外側にある2つの中心（最小値と最大値）の距離に着目します。この距離と移動量K・線分の長さとの関係から、次の3つの場合に分けて判定できます。

• 中心間の距離 ≥ 2K + 線分の長さ の場合：どれだけ移動しても交差は発生しないため、0を返します。
• 中心間の距離 ≥ 2K の場合：移動によって部分的な交差を作ることができるため、「2K −（中心間の距離 − 線分の長さ）」を返します。
• 上記以外の場合：すでに線分全体が交差している状態のため、線分の長さをそのまま返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// 最大交差を求める関数
int max_intersection(int* center, int length, int k) {
   sort(center, center + 3);
   if (center[2] - center[0] >= 2 * k + length) {
      return 0;
   }
   else if (center[2] - center[0] >= 2 * k) {
      return (2 * k - (center[2] - center[0] - length));
   }
   else
      return length;
}
int main() {
   int center[3] = { 1, 2, 3 };
   int L = 1;
   int K = 1;
   cout << max_intersection(center, L, K);
}

出力結果

1

コードの解説

この例では、中心座標 {1, 2, 3} を持つ3つの線分が与えられ、それぞれの長さは L = 1、移動量の上限は K = 1 です。

ソート後、最も外側の中心同士の距離は 3 − 1 = 2 となります。この値は「2K + 長さ = 3」より小さいため交差は不可能ではなく、また「2K = 2」以上であるため部分的な交差が可能です。したがって、計算式「2 × 1 −（2 − 1）= 1」により、最大交差の長さとして 1 が出力されます。

このように、外側の2つの中心の距離に着目するだけで、中央の線分の位置に関係なく答えを効率的に求めることができます。計算量はソート部分が支配的となり、O(N log N)（ここでは要素数3なのでほぼ定数時間）で処理できます。