光の反射 - DISCO presents ディスカバリーチャンネルコンテスト2019 本戦
光の反射 - DISCO presents ディスカバリーチャンネルコンテスト2019 本戦
今年のはじめぐらいにあったオンサイトコンテスト、700点埋めをしてたら避けていた幾何に引っかかったのでやることにした
本番ではDでめっちゃ詰まって時間を溶かしたものの解けなかったので許せねぇ
他人の幾何ライブラリの使い方(beetさん)という気持ちで書いていく
問題概要
平面上に単位円(部屋と呼ぶ)とその中にもう一つの円(柱と呼ぶ)がある。2つの円の間の点が与えられるので、その点から出発して柱に当たらないような直線を引くことができる。このとき、t (0 <= t <= K)
に対して次の質問に答えなさい。
- 直線を単位円内でt回自由に曲げられるとき、直線が到達可能な単位円の円周上の長さを求めよ
問題文
普通にわかりにくくなったので読んで、問題文書く人すごい
解法
正直なところ解法考察パートは100点!みたいな気持ちになる。毎回曲げる場所は円周上にしたくて、曲げる角度は柱への接線にしたいことがわかるため
つまり、実装としては出発地点から柱に向かって右回りと左回りそれぞれ接線上を直進させ続けて円との交点を見つけ、右回りと左周りのたどり着ける限界の点の間の円周はどれぐらいの長さがあるかを知りたい
このとき、途中で右回りと左回りの直線が交差したらそれ以降の答えは1であることもすぐわかる
知りたいこと
- 円周上での限界点間の距離
- 接線
- 接線を引いたときの円との交点
- 途中で交差するかどうか
実装だるそう...という気持ちになるのでこちらを取り出します
https://github.com/beet-aizu/library/blob/master/geometry/geometry.cpp
いつもありがとう、beetさん
beet libraryなので僕は略してbeelって呼んでます
これをまずファイルにコピペしてスタートです。
円周上の限界点間の距離
単位円なので距離は弧度法においての角度になります
右回りでの限界点をr_pt, 左回りでの限界点をl_ptとすると、r_ptから時計回り側のl_ptとの間の角度が答えだとわかる
ここはbeetさんライブラリを使わずにatan2とかいう便利なやつを使う
d1 = atan2(r_pt)
と、d2 = atan2(l_pt)
をして、d1 > d2
であってほしいのでそうでないときはd1 += 2*M_PI
をしてd1 - d2
で大丈夫
接線
ここから先はl_ptとr_ptそれぞれで処理をする
r_ptだけで書くがl_ptでは逆にして書けばいい
接線は、適当に図を書いてゴニョゴニョすると三角比とか数学でわかりそうだな~という気持ちになるが、頭を動かすのをやめてbeetさんライブラリを覗く
なんかtangent(Circle c, Point p)
みたいなのが見つかるのでこれを使います
接点を返してくれるが、2つあるのでどちらを選ぶべきかというと今は右回りを考えているので柱に向かって右側のを選ぶ。これは今いる場所から柱の中心を見て時計回りの方だと考えることができるのでそういうやつがないかライブラリの中を見ます
ccw(Point p0, Point p1, Point p2)
というのが見つかる。これはp0から見てp2がp1のどっち側にあるかを返してくれる。返り値は#define
された定数が返ってくるが今回はこれがCCW_CLOCKWISE
となっている方を選ぶ
auto p = tangent(pillar, r_pt); // pillarは柱 if (ccw(r_pt, pillar.c, p[0]) == CCW_CLOCKWISE) return p[0]; else return p[1];
こんな感じにすればほしい接点が手に入るはず
接線を引いたときの円との交点
r_pt
と接点がわかってるのでこの2つを結ぶ直線と円との交点がほしくなる。
僕は図を書かないとどうやったら求められるかわからないんですが、beetさんライブラリを見るとgetCrossPointCL(Circle c, Line l)
みたいなほしいやつそのままの名前のやつがあるのでこれを使う
これも、円の内側から直線を引くと交点が2つできるんですがr_pt
→ 接点の方向にある点がほしい
これはr_ptから見たベクトルの内積が正だったらいいので、dot(Vector v1, Vector v2)
を見つけてこれを使います
beetさんライブラリではVectorはPointの別名になっていて、Pointは引き算が実装されています
// Point tan_pt ← 接点 auto p = getCrossPointCL(C, Line(r_pt, tan_pt)); // Cは単位円 if (dot(tan_pt - r_pt, p[0] - r_pt)) return p[0]; else return p[1];
これで限界点がわかりました
途中で交差するかどうか
r_pt
から次のr_pt
までの線分と、l_pt
から次のl_pt
まで線分が交差しているかを判定する
次のr_pt
とかは接線を引いたときの円との交点がそれに当たる
線分の交差判定、確かめんどくさいんだよな~という気持ちになりながらbeetさんライブラリを見るとintersectSS(Segment s1, Segment s2)
みたいなほしいやつがあるのでこれを使う
ただ、最初はl_pt
とr_pt
を同じ点で始めるので最初はここで交差したことになってしまうので、適当に弾く。僕は線分の交点が一致していれば気にしないとしたが、l_pt
とr_pt
が一致してれば気にしないようにすれば楽そう
Segment
は端点2つで作れます
// Point new_l_pt, new_r_pt ← 次の限界点的なの Segment s1(l_pt, new_l_pt), s2(r_pt, new_r_pt); if (l_pt != r_pt && intersectSS(s1, s2)) return true; else return false;
適当にフラグを持っておいて、交差したら立ててそれ以降1を出力し続ければいい
これで解けたのでbeetさんありがとうという気持ちになることができる
最初普通に実装方針に迷ってたんですが、どっちが右側かを判定する方法がわからなかっただけで時計回りとかで行けると気づけば終わりだった
ICPCにも適当に改変したりしなかったりして持っていきたいと思います!!!!