点に対する加算とスカラー倍を自然な方法で定義します。例えば、\(A\) と \(B\) の中点は \(\frac{1}{2} A + \frac{1}{2} B\) です。

入力された点を \(P_1, \cdots, P_n\) とし、\(Q\) を打てるか判定しましょう。以下を容易に証明できます。

• \(Q\) を打てる必要十分条件は、以下の条件を満たす係数 \(w_1, \ldots, w_n\) が存在することである。
  • \(w_i\) は非負である。
  • \(w_i\) は有理数であり、分母は \(2\) の累乗である。
  • \(\sum w_i = 1\)
  • \(Q = w_1 P_1 + \cdots + w_n P_n\)

これらの条件は、実は以下と同値であることがわかります。

• \(Q\) が入力点の凸包の外部（境界除く）にある場合、\(Q\) は打てない。
• \(Q\) が入力点の凸包の境界上にある場合、\(Q\) が辺 \(AB\) 上にあるとすると、係数 \(w_i\) は点 \(A, B\) に対応するものを除いて全て \(0\) でなければならない。
• \(Q\) が入力点の凸包の内部（境界除く）にある場合、係数に対する「非負」という条件は無視できる。

この全ての詳細な証明は長くなるため、（最も興味深く難しい部分である）三つ目の部分に対する証明の概略のみを記します。

一般性を失うことなく \(Q\) は原点であると仮定できます。この場合、以下が問題です。

• \(c_i\) を、\(\sum c_i P_i = 0\) を満たす 非負整数 係数とする。\(\sum c_i\) は \(2\) の累乗となりうるか。

これを以下のように変えても真偽は変わらないことを示します。

• \(d_i\) を、\(\sum d_i P_i = 0\) を満たす 整数 係数とする。\(\sum d_i\) は \(2\) の累乗となりうるか。

後者を満たす \(d_i\) があるとき、前者を満たす \(c_i\) の存在を示せれば十分です。まず、\(\sum e_i P_i = 0\) を満たす何らかの 正整数 係数 \(e_i\) をとります。そして、\(s \sum d_i + t \sum e_i\) が \(2\) の累乗であって \(t/s\) が十分大きいような正整数 \(s, t\) をとると、\(c_i := s d_i + t e_i\) が条件を満たします。

これで、主に考えるべきことは以下のようになりました。

• 点 \(Q\) が \(Q = w_1 P_1 + \cdots + w_n P_n\) と書けるのはどのようなときか。ここで、\(w_i\) は以下の条件を満たす係数である。
  • \(\sum w_i = 1\)
  • \(w_i\) は有理数であり、分母は \(2\) の累乗である。

まず、\(w_i\) が \(\sum w_i = 1\) を満たす 整数 係数であるとして、\(w_1 P_1 + \cdots + w_n P_n\) と書ける点全てからなる集合を考えましょう。この集合は、実は非常に単純な構造を持ちます。\(P_i\) のうちいずれかが原点であるとすると、この集合は何らかの点 \(A, B\) に対して以下の形式で書けます。

\(\{ nA + mB | n, m \in \mathbb{Z} \}\)

この点 \(A, B\) は、互除法に似たアルゴリズムで具体的に求められます。

ここで、これらの点が格子点となるような斜交座標系を考えましょう。\(Q\) を打てるのは、この座標系における \(Q\) の座標がともに分母が \(2\) の累乗であるような有理数であるときです。凸領域内のそのような点の個数は、ピックの定理を用いて求められます。