Let’s define additions and scalar products for points in a natural way. For example, the middle point of \(A\) and \(B\) is \(\frac{1}{2} A + \frac{1}{2} B\).

Let \(P_1, \cdots, P_n\) be input points, and check if we can plot \(Q\). It is easy to prove the following:

• We can plot \(Q\) iff there exists coefficients \(w_1, \ldots, w_n\) that satisfies the following conditions:
  • \(w_i\) is non-negative.
  • \(w_i\) is a rational number and its denominator is a power of \(2\).
  • \(\sum w_i = 1\).
  • \(Q = w_1 P_1 + \cdots + w_n P_n\)

And it turns out that these conditions are equivalent to the following:

• In case \(Q\) is strictly outside the convex hull, we can never plot it.
• In case \(Q\) is on the boundary of the convex hull, and it’s on the edge \(AB\), all coefficients \(w_i\) must be zero except for positions corresponding \(A, B\).
• In case \(Q\) is strictly inside the convex hull, we can ignore “non-negative” conditions on coefficients.

The detailed proof of the entire part will be lengthy, so we’ll just write a sketch of the proof for the third part (the most interesting, and difficult part).

Without loss of generality, we can assume that \(Q\) is the origin. In this case, we are interested in the following:

• Let \(c_i\) be non-negative integer coefficients that satisfy \(\sum c_i P_i = 0\). Can \(\sum c_i\) be a power of two?

We claim that the answer doesn’t change even if we change it as follows:

• Let \(d_i\) be integer coefficients that satisfy \(\sum d_i P_i = 0\). Can \(\sum d_i\) be a power of two?

It is enough to show that if we have \(d_i\) satisfying below, we can find \(c_i\) satisfying above. First, let’s take some positive integer coefficients \(e_i\) that satisfies \(\sum e_i P_i = 0\). Then, let’s take some positive integers \(s, t\) such that \(s \sum d_i + t \sum e_i\) is a power of two, and \(t/s\) is large enough. Then, \(c_i := s d_i + t e_i\) satisfies the conditions.

Now, our main concern is as follows:

• When can a point \(Q\) be written as \(Q = w_1 P_1 + \cdots + w_n P_n\), where \(w_i\) are coefficients satisfying below:
  • \(\sum w_i = 1\)
  • \(w_i\) is a rational number and its denominator is a power of \(2\).

First, let’s consider all points that can be written as \(w_1 P_1 + \cdots + w_n P_n\), where \(w_i\) are integer coefficients satisfying \(\sum w_i = 1\). These points actually have a very simple structure. If we assume that one of points \(P_i\) is the origin, this set can be written in the following form for some points \(A, B\):

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

and it’s possible to compute points \(A, B\) explicitly by a gcd-like algorithm.

Then, consider an oblique coordinate system that makes these points integer points. We can plot \(Q\) if both coordinates of \(Q\) in the oblique system are rational numbers with power-of-two denominators. It’s possible to count the number of such points in a convex region by applying Pick’s Theorem.