AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
AtCoder Regular Contest 042 B – アリの高橋くん
直線と点の距離を求めることができれば解ける問題。複素平面の扱いを知っていると解きやすい。
# AtCoder Regular Contest 042 B - アリの高橋くん
# https://atcoder.jp/contests/arc042/tasks/arc042_b
# tag: 計算幾何 基礎問題 高橋君
# 高橋くんの座標を T とする。
# 対象の多角形のすべての辺と T との最短距離のうち、
# もっとも短いものが答えになる。
# T.
#A----B
# の位置関係の時はいいとして、
# T.
# A----B
# の時は大丈夫？となるが、この場合は T がはみ出ている側の
# 隣の辺と T との距離のほうが短くなるので、回答には
# 影響しない。
# T と AB との距離については、
# A を原点に重なるように全ての点を平行移動しておく。
# このときに AB と AT をそれぞれベクトル
# AB(a, b), AT(p, q) として複素平面上に取ると、
# 求めるものは AT / AB * |AB| の y 成分の絶対値となる。
# これは、AB の持つ角度だけ AT を逆に回転してやれば、
# T と AB との距離は T と x 座標との距離になるということ。
# 具体的には、
# (p + qi) / (a + bi) * |AB| =
# (p + qi)(a - bi) / (a + bi)(a - bi) * |AB| =
# ((ap + bq) + (aq - bp)i) / (a^2 + b^2) * |AB|
# より、求めるものは、
# (aq - bp) / (a^2 + b^2) * sqrt(a^2 + b^2)
# 以上を踏まえて……
def main():
x, y = map(int, input().split())
N = int(input())
points = [list(map(int, input().split())) for _ in range(N)]
result = 10**10
for i in range(N):
j = (i + 1) % N
# 点 A, B を取得
ax, ay = points[i]
bx, by = points[j]
a, b = bx - ax, by - ay
p, q = x - ax, y - ay
# 上記考察より、AB と T との距離を求める
dist = abs((a*q - b*p) / (a**2 + b**2) * (a**2 + b**2)**0.5)
if result > dist:
result = dist
print(result)
main()
関連
