#6438. 框出一个正方形

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: dram

题目描述

(本题的最初想法非原创,原始链接有剧透,可参见讨论区)

在平面直角坐标系中,你可以每次选择两个格点( (x,y) ,其中 x y 都是整数的点),然后做出过这两个点的直线。

画出四条这样的直线,可以围成一个正方形,这个正方形具有面积 S

给定面积 S ,是否存在一种方案能围出这个正方形?如果是,请给出一种构造。

我们只考虑有理数 S = p / q 的情况,而你的输出也必须是精确解。

举例:

  • 1/2 5/2 4/5 可以构造
  • 1/4 2/3 不能构造
  • 12/15 就是 4/5 ,所以可以构造

例如,下面是一个 4/5 的构造

输入格式

第一行是一个整数 T ,表示总共有 T 组询问

之后 T 行,每行两个整数 p q 0 < p, q < 5 \times 10^6 ),表示本次询问的是 S = p/q 的构造。

输出格式

对于每组询问,输出一行:

  • 如果给出的面积 S 可以构造,输出 16 个空格分隔的整数表示你的构造,包含:
    • 4 条能围成面积为 S 的正方形的线(不必在意线的顺序)
    • 每条线 2 个点
    • 每个点两个整数 x y 表示 (x, y) 这个点,其中, -2^{64} < x, y < 2^{64} (参见“数据范围与提示”)
  • 否则,面积 S 不能构造,输出一行 impossible

样例

样例输入

2
1 3
4 5

样例输出

(一个可以接受的输出)

impossible
0 0 1 2 1 2 3 1 2 2 1 0 1 1 3 0

这里给出的 4/5 的构造即是上文图中的构造,给出的 4 条线依次是 EA, AB, GF, DC

数据范围与提示

总共有 10 个测试点,每个测试点记 10 分。其中:

  • 测试点 1 的输入如下:
    5
    4999889 3988009
    4012009 4999762
    3674633 4999348
    4997709 2000066
    4782969 1953125
    
  • 对于测试点 2 \dots 5 T = 1
  • 对于测试点 6 \dots 10 T = 20000

虽然检查器使用高精度整数读入答案,但是极不推荐输出绝对值超过 2^{64} 的坐标值 x y 。这一点不应在解题过程之中产生限制。如果因坐标值绝对值过大且超出此范围,而导致无法正常评测,本题作者不接受为解决此问题改动题目的请求。