题目描述

Bobo is exploring a set of lattice points on a two-dimensional plane. Initially, the set of points is defined as $S=\{(0,0),(A,0),(0,B),(A,B)\}$ . Bobo's goal is to include a specific lattice point $(X, Y)$ in $S$. To achieve the goal, Bobo may
 perform the following operation:

• Select two lattice points $P,Q\in S$ such that $\frac{P+Q}{2}$ is also a lattice point, and add $\frac{P+Q}{2}$ to $S$ .

Your task is to help Bobo find a sequence of operations that minimizes the number of steps to achieve the goal or determine if it is
impossible to do so.

输入格式

The first line of the input contains two integers $A$ and $B$ ($0 ≤ A, B ≤ 10^9$), describing the parameters of the initial lattice points.

The second line of the input contains two integers $X$ and $Y$ ($0 ≤ X ≤ A, 0 ≤ Y ≤ B$), denoting the coordinates of the target lattice
point.

输出格式

If it is impossible to achieve the goal, output $-1$ in one line. Otherwise, output a single integer $k$ ($0\le k\le10^5$) in one line, denoting the 
total number of operations to perform. Then $k$ lines follow. The $i$-th line contains four integers $U_i,V_i,S_i,T_i$ ($0\le U_i,V_i,S_i,T_i\le 10^9$), describing the lattice points $P=(U_i,V_i)$ and $Q=(S_i,T_i)$ chosen in the $i$-th operation. If there exist multiple solutions, output any.

2 2
1 1

1
0 0 2 2

8 8
5 0

3
0 0 8 0
4 0 8 0
4 0 6 0

0 0
0 0

0

2024 0
1012 0

1
0 0 2024 0

2024 2024
2023 2023

-1

8 6
7 3

3
0 0 8 0
4 0 8 0
6 0 8 6

题目大意

给定初始格点集合 $S=\{(0,0),(A,0),(0,B),(A,B)\}$ ，通过尽可能少的添加中点操作得到格点 $(X,Y)$。

• 添加中点操作：是指从集合 $S$ 中选择两个点，得到他们的中点，然后加回集合 $S$ 。

题目来源

2024-CCPC中国大学生程序设计竞赛-郑州站 - C题