答えは、連続時間を総当たりする代わりに、x・yの4つのmax/min envelopeに含まれる直線の非負交点と初期時刻だけを比べることです。ABC130 F「Minimum Bounding Box」の問題文は、速さ1で軸に沿って動く全点を同じ時刻に止め、囲む長方形の面積を最小化します。方向を傾き−1、0、+1の座標直線へ置き換えると、面積の候補時刻を有限個に絞れます。
停止時刻はt ≥ 0で、t=0も選べます。問題の制約は1 ≤ N ≤ 105、各座標は−108 ≤ x_i, y_i ≤ 108、出力は絶対誤差または相対誤差10−9以下です。
方向を座標の直線に置き換える
点の速さは1なので、方向ごとに変化する座標だけが時間の傾きを持ちます。各座標はm*t+bの形になり、mは−1、0、+1のいずれかです。
| 方向 | x座標 | y座標 |
|---|---|---|
R |
x_i(t) = x_i + t |
y_i(t) = y_i |
L |
x_i(t) = x_i − t |
y_i(t) = y_i |
U |
x_i(t) = x_i |
y_i(t) = y_i + t |
D |
x_i(t) = x_i |
y_i(t) = y_i − t |
ある時刻の横幅と縦幅を、それぞれW_x(t) = X_max(t) − X_min(t)、W_y(t) = Y_max(t) − Y_min(t)とします。ここでX_max(t) = max_i x_i(t)、X_min(t) = min_i x_i(t)であり、Y_maxとY_minも同様です。求める面積はA(t) = W_x(t) × W_y(t)です。
同じ傾きの直線は切片の極値だけ残す
たとえばx_i(t) = t + bという傾き+1の直線が何本あっても、最大値を取る側では切片bが最も大きい1本だけが必要です。同じ傾きなら、時刻によらず切片の大小関係が変わらないからです。最小値を取る側では切片が最も小さい1本だけを残します。傾き−1、0でも同じです。
この圧縮で、X_max、X_min、Y_max、Y_minの各envelopeは最大3本になります。候補を作るときは、4つのenvelopeそれぞれについて、傾きの違う直線どうしの交点をすべて計算し、t ≥ 0のものを集めます。交点はm_1*t + b_1 = m_2*t + b_2を解いたt = (b_2 − b_1) / (m_1 − m_2)です。これにt=0を加え、その時刻の面積を比較します。
実際にはenvelopeの担当直線が切り替わらない交点も候補に入りますが、どれも問題で許された時刻です。余分な候補があっても最小値を誤らず、各envelopeは最大3本なので、候補時刻は重複を除いて最大13個です。
同時切替を t=0、t=1、t=2 で追う
次の4点を考えます。(2, 0, L)、(0, 0, R)、(0, 2, D)、(0, 0, U)です。横方向では上端の候補が2 − tとt、縦方向でも2 − tとtになり、どちらもt=1で切り替わります。下端はどちらの軸も0です。
| 時刻 | x座標（4点） | x幅 | y座標（4点） | y幅 | 面積 |
|---|---|---|---|---|---|
0 |
{2, 0, 0, 0} |
2 |
{0, 0, 2, 0} |
2 |
4 |
1 |
{1, 1, 0, 0} |
1 |
{0, 0, 1, 1} |
1 |
1 |
2 |
{0, 2, 0, 0} |
2 |
{0, 0, 0, 2} |
2 |
4 |
t=1では横幅・縦幅がともに1になり、面積は1です。この例ではt=0とt=2の面積は4なので、切替時刻が最小を与えています。横と縦の交点が同じ時刻でも、候補集合ではその時刻を1つとして扱えます。
区間内の面積の最小も端点にある
候補時刻を時間順に並べると、隣り合う時刻の間では各envelopeを担当する直線が変わりません。その区間では幅が一次式になり、W_x(t) = a_x*t + b_x、W_y(t) = a_y*t + b_yと書けます。幅は負にならず、面積はA(t) = W_x(t) × W_y(t)という二次式です。
a_xとa_yが同じ符号なら、両方の幅が同時に増えるか、同時に減るため、面積も単調に変化します。どちらかの傾きが0の場合も、面積は一次式または定数です。符号が逆なら、面積の二次係数はa_x × a_y < 0です。このとき導関数は減少し、区間の内部で導関数が0になる点があればそこは最大点です。最小点は区間の端にあります。したがって区間内の二次式の停留点を最小候補に加える必要はありません。
AtCoder公式日本語解説PDFの7ページ、F節も、極値の変化率が一定となる区間を作り、区間端点を比べる考え方を説明しています。ここで使う同傾きの切片圧縮と全交点列挙は、公式コードの転載ではなく、問題文の速度式から候補を作る導出です。
最後の交点より後では、各max envelopeで利用可能な最大の傾き、各min envelopeで最小の傾きが有効になります。そのため横幅・縦幅の傾きはどちらも0以上で、面積は減りません。最後の交点を調べれば無限に続く時間を別途探索する必要もありません。
Python 3の完全コード
コードは入力を1回読み、傾きごとに切片の最小値・最大値を保持します。その後、4つのenvelopeの交点と初期時刻を評価します。
import sys
def update_group(extrema, slope, value):
bounds = extrema[slope]
if bounds[0] is None or value < bounds[0]:
bounds[0] = value
if bounds[1] is None or value > bounds[1]:
bounds[1] = value
def build_envelopes(extrema):
upper = []
lower = []
for slope, (smallest, largest) in extrema.items():
if smallest is None:
continue
upper.append((slope, largest))
lower.append((slope, smallest))
return upper, lower
def add_crossings(lines, times):
for i in range(len(lines)):
m1, b1 = lines[i]
for j in range(i + 1, len(lines)):
m2, b2 = lines[j]
if m1 == m2:
continue
t = (b2 - b1) / (m1 - m2)
if t >= 0:
times.add(t)
def span_at(upper, lower, t):
return max(m * t + b for m, b in upper) - min(
m * t + b for m, b in lower
)
def solve():
stream = sys.stdin.buffer
first = stream.readline()
if not first:
return
n = int(first)
x_extrema = {slope: [None, None] for slope in (-1, 0, 1)}
y_extrema = {slope: [None, None] for slope in (-1, 0, 1)}
for _ in range(n):
x, y, direction = stream.readline().split()
x = int(x)
y = int(y)
if direction == b"R":
sx, sy = 1, 0
elif direction == b"L":
sx, sy = -1, 0
elif direction == b"U":
sx, sy = 0, 1
else:
sx, sy = 0, -1
update_group(x_extrema, sx, x)
update_group(y_extrema, sy, y)
x_upper, x_lower = build_envelopes(x_extrema)
y_upper, y_lower = build_envelopes(y_extrema)
times = {0.0}
for lines in (x_upper, x_lower, y_upper, y_lower):
add_crossings(lines, times)
answer = min(
span_at(x_upper, x_lower, t) * span_at(y_upper, y_lower, t)
for t in times
)
print(answer)
if __name__ == "__main__":
solve()
境界条件と計算量
timesは{0.0}から始めるので、停止可能な最初の時刻を必ず調べます。交点はt ≥ 0のものだけ加え、負の交点は除外します。t=0の交点や複数のenvelopeが同時に切り替わる時刻は、setで1つにまとまります。- 平行な直線は
m_1 = m_2なので有限の交点を持たず、コードでも計算を飛ばします。観測されない傾き群はNoneのままにしてenvelopeへ追加しません。N ≥ 1なので、各軸のmax/minには少なくとも1本の直線が残ります。 - 交点の分子は整数、傾きの差は1または2なので、交点は整数または半整数です。座標制約から交点の絶対値は最大でも
2 × 108で、この範囲の整数と半整数はbinary floatで正確に表せます。同じ時刻の交点はsetで同一値になり、epsilonで近い別時刻を誤ってまとめる必要はありません。
点を1回走査する時間はO(N)です。各envelopeは最大3本なので交点の生成と評価は定数回で、補助状態は入力・出力バッファを除いてO(1)です。
標準入力での検算結果
掲載コードそのものを標準入力で実行しました。公式サンプルは問題ページのSample Input/Output 1〜3、独自例はSOURCEで固定した入力です。
| 区分 | ケース | 期待値 | ローカル出力 |
|---|---|---|---|
| 公式サンプル | 1 | 0 |
0.0 |
| 公式サンプル | 2 | 97.5 |
97.5 |
| 公式サンプル | 3 | 273 |
273.0 |
| 独自例 | 横・縦の同時切替が最小 | 1 |
1.0 |
| 独自例 | 初期時刻が最小 | 4 |
4.0 |
| 独自例 | RだけでL/U/D群なし | 6 |
6.0 |
初期時刻が最小の入力はN=4と点(1, 1, R)、(−1, −1, L)、(−1, 1, U)、(1, −1, D)です。初期時刻の面積は4で、その後は両幅が増えます。速度群欠落の入力はN=2と点(0, 0, R)、(2, 3, R)で、幅は変わらず面積6です。
このコードはAtCoderへ提出していません。ここで示したのはローカル実行の結果であり、ACや公式ジャッジ通過を示すものではありません。
