Zenn
✨

AGC036 A Triangle解説[python]

2021/01/07に公開
Python
AtCoder
競プロ
構築
幾何
tech

URL

https://atcoder.jp/contests/agc036/tasks/agc036_a

問題概要

  • xy 平面上でx,yともに0~10**9 までの整数値を取る点を3点とった時その三点からなる三角形の面積がS/2となるような3点の座標を１つ求めよ
  • 1<=S<=10**18

提出コード

s = int(input())
c, a, b, d = 1, 10 ** 9, 1 + s // (10 ** 9), 10 ** 9 - s % (10 ** 9)
if s % (10 ** 9):
    print(0, 0, c, a, b, d)
else:
    print(0, 0, c, a, b - 1, 0)
# print(a * b - c * d)

考察

  • 幾何の問題：三角形の性質を考える
    • 鋭角な三角形を考えると展開することができる。
  • 1点をできるだけ広くとるために(0,0)におき他の2点を(a,c),(b,d)とする
  • その時の面積は(ab-cd)/2 となるため10^9以下という制約でS=ab-cdとなるa,b,c,d を求める問題に言い換えられる
  • a = 10^9 に固定して考えるとb=S//10^9 にすれば、c*d はS%10^9で10^9以下になるためa=10**9,b=s//(10**9),c=1,d=s%(10**9)にすれば条件を満たす

実装方針

メモ

  • 幾何かと思ったら思いっきり数学だった。
  • できるだけ簡単なケースを考えるためにa=10**9に固定したところがミソ

参考

Discussion