Codeforces 296 DIV1 B Clique Problem
続き。
こどふぉの問題ですね。 普通にわからんかったので、色々調べました。
問題概要
数直線上に位置 x_i と 重み w_i を持つ点 N が与えられる。この点から、 どの 2 点を選んでも|x_i - x_j| >= w_i + w_jを満たすグラフの最大頂点数を求める。
解法
これは、x_i-w_i~x_i+w_i を区間とする区間スケジューリング問題に帰着するらしい。
これを図に表すと、
こんな感じになる。
これが、重ならない組み合わせの最大個数を求めることになる。ほへぇ、すげぇ。
n = int(input())
d = []
for i in range(n):
xx, ww = [int(i) for i in input().split()]
d.append([xx-ww, xx+ww])
d.sort(key=lambda x:x[0])
last = -100000000000
ans = 0
for i in range(n):
if last <= d[i][0]:
last = d[i][1]
ans += 1
elif last > d[i][1]:
last = d[i][1]
print(ans)
