ABC 139 F - Engines【Python】
問題はこちら。
想定解法とちょっと違う。例えばすべてのベクトルが y > 0 という半平面に入っている場合を考える。すべてのエンジンを使うか使わないかで場合分けすると計算量がO(2^N)になって死ぬ。だが実際は到達可能な点すべてを含む凸胞の頂点のみを調べればよいのでO(N)で済む。凸胞の求め方はベクトルを偏角ソートして小さい順(大きい順)に累積和をとればよい。ソートする部分がボトルネックになって計算量はO(N log N)。
import sys
readline = sys.stdin.readline
def main():
N = int(readline())
pos, neg = [], []
for _ in range(N):
x, y = map(int, readline().split())
if x == y == 0:
continue
if y > 0 or y == 0 and x > 0:
pos.append([x, y])
else:
neg.append([x, y])
pos.sort(key=lambda x: x[0] / (x[0]**2 + x[1]**2)**0.5)
neg.sort(key=lambda x: x[0] / (x[0]**2 + x[1]**2)**0.5)
s_pos = [[0, 0] for _ in range(2 * len(pos) + 1)]
s_neg = [[0, 0] for _ in range(2 * len(neg) + 1)]
for i in range(len(pos)):
s_pos[i + 1][0] = s_pos[i][0] + pos[i][0]
s_pos[i + 1][1] = s_pos[i][1] + pos[i][1]
s_pos[-i - 1][0] = s_pos[-i][0] + pos[-i - 1][0]
s_pos[-i - 1][1] = s_pos[-i][1] + pos[-i - 1][1]
for i in range(len(neg)):
s_neg[i + 1][0] = s_neg[i][0] + neg[i][0]
s_neg[i + 1][1] = s_neg[i][1] + neg[i][1]
s_neg[-i - 1][0] = s_neg[-i][0] + neg[-i - 1][0]
s_neg[-i - 1][1] = s_neg[-i][1] + neg[-i - 1][1]
ans = 0
for x_pos, y_pos in s_pos:
for x_neg, y_neg in s_neg:
ans = max(ans, ((x_pos + x_neg)**2 + (y_pos + y_neg)**2)**0.5)
print(ans)
if __name__ == '__main__':
main()
この記事が気に入ったらサポートをしてみませんか?