// 拡大率の条件漏れ (3) #include #include #include #include const std::string Possible{ "Possible" }; const std::string Impossible{ "Impossible" }; /** * D は q の倍数とする。k=D/q: 拡大率 * * R=floor(q/p) として、次のような山(実線)を i=0,1,...,R まで並べる * * x=i(kp-1) * : x=i(kp+1) 山の内側の点線 (山 i-1 を kp だけ右にシフトしたもの): 通行禁止 * : : * +-------+ y=i * | ..... | * | : : | * | : : | * | : : | * | : : | * | : : +----- y=-R+i * ---------+ : :....... * ...........: * * [拡大率 k (=D/q) が満たすべき条件] * 1. R(kp+1)-R(kp-1) < kp : R番目の山の幅が kp 未満 * 2. kq - R(kp-1) < kp : R番目の山の左端と kq(=D) の距離が kp 未満 * 3. R(kp+1) <= kq : R番目の山の右端より右側 (inclusive) に kq(=D) が存在 * * それぞれ整理すると * 1. k >= ceil((2R+1)/p) * 2. k >= ceil((R+1)/(p(R+1)-q) * 3. k >= ceil(R/(q-pR)) * * つまり k は 1,2,3 の右辺の最大値を取れば十分 * * [線分の長さ] * - x 方向: kq * - y 方向: R((R+1)+R)+R = 2R(R+1) * * R,k,q の最大値は? * - R: 249 * - k: 250 * - q: 500 * * 結局 kq + 2R(R+1) <= 249500 なので長さの制約は OK * * [座標の大きさ] * - x 方向: 0<=x<=kq なので |x|<=125000 で OK * - y 方向: -R<=y<=R なので |y|<=500 で OK */ void debug(const std::vector>& points) { int maxx = 0; int miny = 0, maxy = 0; for (const auto& [x, y] : points) { maxx = std::max(maxx, x); miny = std::min(miny, y); maxy = std::max(maxy, y); } std::vector lines_(maxy - miny + 1, std::string(maxx + 1, ' ')); auto lines = lines_.rend() - (maxy + 1); for (int x = 0; x <= maxx; ++x) { lines[0][x] = '.'; } lines[0][0] = '+'; for (size_t i = 1; i < points.size(); ++i) { auto [px, py] = points[i - 1]; auto [cx, cy] = points[i]; if (i + 1 == points.size()) { lines[cy][cx] = '+'; } else { auto [nx, ny] = points[i + 1]; bool cv = px == cx; bool nv = cx == nx; if (cv != nv) { lines[cy][cx] = '+'; } else if (cv) { lines[cy][cx] = '|'; } else { lines[cy][cx] = '-'; } } } for (auto& line : lines_) { std::cerr << line << '\n'; } std::cerr.flush(); } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int p, q; std::cin >> p >> q; if (p == 1) { std::cout << Impossible << '\n'; return 0; } std::cout << Possible << '\n'; const int R = q / p; const int k = std::max( { 2 * R / p + 1, R / (p * (R + 1) - q) + 1, // (R + q - p * R - 1) / (q - p * R) } ); std::vector> points; // 山 i for (int i = 0; i < R; ++i) { int x = i * (k * p + 1); int y = i; // 山 i を下る while (y > -R + i) { points.emplace_back(x, y); --y; } // 山 i と i+1 の間の谷の右端まで移動 while (x < (i + 1) * (k * p - 1)) { points.emplace_back(x, y); ++x; } // 山 i+1 を上る while (y < i + 1) { points.emplace_back(x, y); ++y; } // 山 i+1 の峰の右端まで移動 while (x < (i + 1) * (k * p + 1)) { points.emplace_back(x, y); ++x; } } // 山 R { int x = R * (k * p + 1); int y = R; // 山 R を下る while (y > 0) { points.emplace_back(x, y); --y; } // (D,0) まで進む while (x <= k * q) { points.emplace_back(x, y); ++x; } } std::cout << points.size() - 1 << '\n'; for (const auto& [x, y] : points) { std::cout << x << ' ' << y << '\n'; } }