#P16562. [Bapc2021]Kinking Cables

[Bapc2021]Kinking Cables

题目描述

你需要用一根长度固定的电缆连接两台计算机,并且必须恰好使用完整的电缆长度。

房间是一个 n×mn\times m 的矩形。第一台计算机位于左上角 (0,0)(0,0),第二台计算机位于右下角 (n,m)(n,m)。

电缆由一列标记点

p1,p2,…,pkp_1,p_2,\ldots,p_k

描述。依次用直线段连接相邻标记点,即得到电缆的路径。该路径必须满足:

  1. 路径从 (0,0)(0,0) 开始,在 (n,m)(n,m) 结束。
  2. 所有标记点和线段都位于矩形房间内部或边界上。
  3. 除相邻线段在共同端点处相接外,路径中的线段不能相交。
  4. 对任意标记点 pip_i,除相邻的 pi−1p_{i-1} 和 pi+1p_{i+1} 外,不得存在其他标记点与 pip_i 的欧氏距离严格小于 11。
  5. 路径总长度必须恰好等于给定的 ℓ\ell。

请构造任意一条满足所有条件的电缆路径。

输入格式

第一行包含两个整数 nn 和 mm,表示房间的两个边长。

第二行包含一个浮点数 ℓ\ell,表示电缆长度。

输出格式

第一行输出一个整数 kk,表示路径中的标记点数量。

接下来 kk 行,每行输出两个浮点数 xx 和 yy,表示一个标记点的坐标。各点必须按照电缆路径上的先后顺序输出。

必须满足

2≤k≤500,2\le k\le 500, 0≤x≤n,0≤y≤m.0\le x\le n,\qquad 0\le y\le m.

路径总长度与 ℓ\ell 的绝对误差或相对误差不超过 10−610^{-6}。

若有多种合法方案,输出任意一种即可。

数据范围

2≤n,m≤100,2\le n,m\le 100, n2+m2≤ℓ≤n⋅m.\sqrt{n^2+m^2}\le \ell\le n\cdot m.

样例 1

输入

3 4
5.0

输出

2
0 0
3 4

样例 2

输入

3 4
7.0

输出

3
0 0
3 0
3 4

样例 3

输入

5 5
11.5

输出

7
0 0
2 0
2 1.75
4 1.75
4 1
5 1
5 5