競技プログラミング用 知識集積所
ARC200A - Dot Product
最終更新：
sport_programming
-
view
問題
必要知識
簡単な内容は省略
考え方
とりあえず、1つの場合は明らかに無理として、2つの場合を考えてみる。
つまり、
つまり、
a1*x1 + a2*x2 > 0 b1*x1 + b2*x2 < 0
とできるx1とx2を考えてみる。
上の式の左辺が+c、下の式の左辺が-cになるとして、行列を使うと
|a1 a2| |x1| | c| |b1 b2| |x2| = |-c|
となる。
ここで行列式a1*b2-a2*b1>0である場合、
|x1| | b2 -a2| | c| |x2| = |-b1 a1| |-c| * 1/(a1*b2-a2*b1)
で、c=a1*b2-a2*b1とすると、
x1 = a2+b2 x2 = -a1-b1
となる。
これはXの取りうる値の範囲に収まっている。
これはXの取りうる値の範囲に収まっている。
a1*b2-a2*b1>0である場合は、c=-(a1*b2-a2*b1)とすることで、
x1 = -a2-b2 x2 = a1+b1
となる。
a1*b2-a2*b1=0である場合は、どんなXを用意しても、内積は絶対に正の定数倍の関係になるので、異符号にならず不可能。
以上が2つの場合の話である。
では3つ以上の場合。
では3つ以上の場合。
全ての場所でa/bの値が一定であれば、どんなXを用意しても、内積は絶対に正の定数倍の関係になるので、異符号にならず不可能。
それ以外の場合にはどこかにa/bが異なる組み合わせがあり、その2か所だけを使って前述の方法でXを求め、他は全て0にしておけばよい。
それ以外の場合にはどこかにa/bが異なる組み合わせがあり、その2か所だけを使って前述の方法でXを求め、他は全て0にしておけばよい。
