geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCodet Beginner Contest 259 参加記録

ベクトルの回転 ABC Union-Find

コンテスト中AC:A〜D

B - Counterclockwise Rotation

ベクトルの反時計回りの回転行列は以下の通りです。

よって、求めたい座標を $(p,q)$ とすれば、
$p=a\cos d - b\sin d$
$q=a\sin d + b\cos d$

となります。
但し、C++では角度はラジアンにしないといけないので、 $r\leftarrow \frac{d\pi}{180}$ として、 $d$ の代わりに $r$ を渡します。

実装は、ようやくベクトルの回転をライブラリ化したので、それを載せておきます。
Submission #33246511 - AtCoder Beginner Contest 259

D - Circumferences

円 $i,j$ 及び $j,k$ が交点を持つなら、点は $i,k$ 間を移動できます。
このように点が行き来できるような円の関係はUnion-Findで管理できます。

Union-Findにおいて、円 $i,j$ が同グループとなる条件は、円 $i,j$ が交点を持つことです。
この条件ですが、Web検索して以下を見つけました。

www.mathlion.jp

というわけで、円の全組を全探索し、以下の条件を満たし、交点を持たない場合以外にはグループ化します。

$a\leftarrow (r_i + r_j)^2$
$b\leftarrow (x_i - x_j)^2 + (y_i - y_j)^2$
$c\leftarrow (r_i - r_j)^2$
とした時、
$b\gt a\ \lor\ b\lt c$

誤差が怖いので、全て2乗で考えました。
半径の大小関係が規定されていたので、念のため $r_i \gt r_j$ の場合に判定することにしました（おそらく2乗するので必要ないです）。

グループ化した後は、点 $(s_x , s_y)$ を通る円 $i$ と、点 $(t_x , t_y)$ を通る円 $j$ がグループであるかを全探索し、1つでも同グループがあればYes、1つもなければNoとなります。

この全探索の前準備として、点 $(s_x , s_y)$ を通る円を配列 $S$ に記録します。
点 $(t_x , t_y)$ を通る円も同様に配列 $T$ に記録します。

点 $(a,b)$ が円 $i$ 上にあるかは、 $x_i^2 + y_i^2 = r_i^2$ に代入して、 $a^2 + b^2 = r_i^2$ を満たせば良いです。

計算量は、グループ化させていくところがボトルネックとなり、 $O(N^2 \alpha (N))$ だと思います。
$\alpha (N)$ はアッカーマン関数の逆関数です。

Submission #33105175 - AtCoder Beginner Contest 259