review-C

Problem C
Visible Squares
(出典)
South America 1998 Problem 4
問題の概要 (1)
 第一象限内の正方形がいくつ見えるか？
問題の概要 (2)
 第一象限内の正方形がいくつ見えるか？
解釈
 定義通りにするなら, 2本の辺で計算
 結構面倒
 角度を使って計算しても良い
 これだと2本の辺をまとめて扱える
 前の図を見ると直感的ですよね？
解法いくつか
 外積を使って三角形の内外判定
 これではなかなかうまくいかない
 角度に対する, 区間処理
 Naiveに
 Priority queueを使って
 モンテカルロ
 もちろん適さない (Yes/Noではないのだから)
区間による計算 (1)
 横軸に角度, 縦軸に距離をとってみる
距離
角度
 区間の計算は実践演習でよくやった
区間による計算 (2)
 縦軸の距離はどうやって求める？
 それなりに方法がありそう
 簡単なのは, 右下りの対角線のy切片の値
 交わらないなどの性質を使う
 これを間違えると, 微妙な値の差が生じる
区間の計算の別のやりかた
 区間の境界値だけ求める
 2N個の境界値
 連続する2つの境界値について,
 その中点がどれに所属するか求める
 区間の幅が0なら, 考慮しないといけない
 でも, この場合は大丈夫
距離
角度
区間の計算の別のやりかた
 区間の境界値だけ求める
 2N個の境界値
 連続する2つの境界値について,
 その中点がどれに所属するか求める
 区間の幅が0なら, 考慮しないといけない
 でも, この場合は大丈夫
距離
角度
ところで…
 正解が21のところ,何を勘違い？
 900以上とか,
 2倍くらいの値とか
 12や13とか…
 どうやって解いた？
 Gokuri-Squeezeは, 1発通過
 Wihhyは3回目

Download Report