More Related Content
More from Takumi Yamashita (20)
Recently uploaded (6)
L : 解説
- 1. Problem L: RedBlue 原案, 解説: 10% テストケース作成等: moti
- 4. 解法 ● 幾何 + 最小费用流(コスト最小二部マッチング)
- 5. 解法(幾何 パート) ● 必要なもの ○ ある点を通る円の接線 ○ 円と線分の交差判定 ○ 直線と直線の交差判定および交点
- 6. 解法(幾何 パート) ● すべての赤い点とすべての青い点との間の最小距離を求める ● 2点間の最小距離は、以下の距離の最小値である ○ 2点間を直線で結んだときの距離 (ただし、この線分は円と交差しない ) ○ 赤い点を通る円の接線と青い点を通る円の接線の 2つの直線の交点を求める。この交点から赤い 点への距離+交点から青い点への距離 円の接線は、2つの円があり、各点最大 4つずつあるのですべての組み合わせを試してそのときの 最小値をとる
- 9. 解法(幾何 パート) ● 接線 d1 d2 青の点を通る円の接線と赤の点を通る円の接線の 交点を黒い点としたとき、 2点間の距離 = d1 + d2 で表される。 これをすべての組み合わせについて調べる。
- 10. 解法(フロー パート) ● 幾何パートで求めた2点間の最小距離dab をコストとしてエッジをはる。なお、dab は 赤い点aと青い点bとの最小距離を表す S T 1 2 N . . . 1’ 2’ N’ 赤い点 青い点 0(1) 0(1) 0(1) 0(1) 0(1) 0(1) コスト(キャパシティ) d11’ (1) d1N ’ (1) dNN’ (1) d22’ (1) d N2’ (1)
- 13. 結果 ● Onsite ○ First Submission: ( min) ○ First AC: ( min) ● Online ○ First Submission: codera_iroha ( 240 min) ○ First AC: anta ( 240 min)
- 14. ジャッジ解 moti C++ 249行 kzyKT C++ 166行 arrows C++ 269行 sate C++ 227行