Codeforces Round #466 (Div. 2) + AtCoder Grand Contest 021
-
masashinakata
- 2068
- 0
- 0
- 0
-
- いいね！0
フェリン
@ferin_tech15
ac:879 (+2) cf:127 (+0) srm:69 (+2) aoj:264 (+0) yuki:108 (+0) csa:6 (+0) spoj:2 (+0) All:1455 (+4)
2018-02-25 08:06:06
nico_shindannin（診断人）
@nico_shindannin
AGC021 B 穴とすぬけの距離 = (x-Rcosθ)^2 + (y-Rsinθ)^2 = R^2-2R(xcosθ+ysinθ)+x^2+y^2 R→∞で、最小値をとる穴(xi,yi)を求めたいけど、 ・Rは穴によらず固定 ・x^2+y^2はRに比べて小さすぎるので無視できる かわりに、(xcosθ+ysinθ)の最大値をとる穴を求めればokじゃ。
2018-02-25 08:33:33
nico_shindannin（診断人）
@nico_shindannin
Rにdoubleで精度で死なない値を入れようとか変なこと考えてたせいで、R=10^9とかR=10^12とか変な試行錯誤をして何回か落としてしまったけど、最初から数式で考えてれば、そんなことする必要はなかった…。だめじゃ。
2018-02-25 08:37:32
nico_shindannin（診断人）
@nico_shindannin
むしろB問題でなぜ凸包が出てくるのか分かってないのじゃ…。（最初ボロノイ図は考えてましたが、すぐ捨てた）
2018-02-25 08:48:30
Noimin
@noisy_noimin
AtCoder 28AC目 AGC021 B - Holes (600) beta.atcoder.jp/contests/agc02… 昨日のBを，大きな円に点を等間隔で置いて最後に点の個数で割る解法で解いた．最初計算が合わなかったのは大きなRを乗じたりしてオーバーフローしてたみたい．凸包解法も勉強してみますか〜
2018-02-25 11:47:52
satanic@研究💪
@satanic0258
@masashinakata どんなケースかは把握してないのですが， agc021.contest.atcoder.jp/submissions/21… の166行目で上記式を求めたあとacosを取ると定義外エラーが1ケースで出て， agc021.contest.atcoder.jp/submissions/21… ではacos直前に定義域を超えてたら上限に詰める操作を行うとACになったんですよね (ただ演算誤差が出ただけなのかもしれませんが)
2018-02-25 12:09:11
ヘクト🐬
@osrehun
ARC 086 E いつかのJAG春コンテストを彷彿とさせる。(どう書くべきなんだこういうの?) beta.atcoder.jp/contests/arc08…
2018-02-25 23:40:56
ヘクト🐬
@osrehun
beta.atcoder.jp/contests/cf16-… 解説を見ましたが、三角形の内部(辺上も含む) の2点間の距離の最大値は3辺の最大値と一致するの直感的には分かるけど、ちゃんと証明するの大変だな...
2018-02-26 00:34:58