145. 平面内の円とベクトル

【問題概要】
平面内に n 個の円があります。それぞれの円は、中心の座標と半径で表されます。また、平面内に m 個のベクトルがあります。それぞれのベクトルは、始点と終点の座標で表されます。ベクトルには、それぞれ重み w_i が割り当てられています。各ベクトルについて、以下の操作を行った後の、そのベクトルの重みを求めてください。

ベクトルが通過するすべての円のうち、半径が最も小さいものの半径を r とする。
重みを 1 とし、半径 r に接するように円を無限に並べたときに、ベクトルが円の内側にあるならば重みを 2 倍して、そうでない場合は 2 倍しない。

【解説】
与えられたベクトルが通過する円のうち、最小の半径を求めるためには、与えられたすべての円との交点を求めて、そのうち最小の半径を持つ円を特定すれば良いです。この操作には、二次方程式を解いて交点を求める必要があります。

その後、半径 r に接するように円を無限に並べたときに、ベクトルが円の内側にあるかどうかを判定する必要があります。この操作には、点と円の位置関係を調べる必要があります。具体的には、ベクトルの始点から円の中心までの距離が半径より小さければ、ベクトルは円の内側にあると判定します。

以上の操作をすべてのベクトルについて繰り返すことで、各ベクトルの重みを求めることができます。

Atcoderで類似の問題は、「Codeforces Round #622 (Div. 2) F - Euclid's nightmare」(https://codeforces.com/contest/1296/problem/F) です。
レーティング難易度(★): 2700
ACした回答者に絞った場合のレーティング帯の範囲(数値): 2800~3100
レーティング難易度(%): 2.0%
レーティング(数値): 2902
AC率(%): 13.3%
ACしたスコアの高い回答者: tourist, ecnerwala
解説ブログ: https://codeforces.com/blog/entry/73172