Contest Duration: - (local time) (270 minutes) Back to Home

## E - Middle Point Editorial by rng58_admin

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.

posted:
last update: