QOJ.ac

QOJ

Limite de temps : 1 s Limite de mémoire : 1024 MB Points totaux : 100

#11958. 避开深渊

Statistiques

你正站在一个具有整数坐标 $(x_s, y_s)$ 的点上。你想要走到具有整数坐标 $(x_t, y_t)$ 的点。为此,你可以沿着一系列线段行走。但是,你的路上有一个游泳池。游泳池是一个轴对齐的矩形,其左下角位于点 $(x_l, y_l)$,右上角位于点 $(x_r, y_r)$。你绝对不能穿过游泳池,甚至不能触碰它的边界。然而,天很黑,你不知道 $(x_l, y_l)$ 和 $(x_r, y_r)$ 的坐标。相反,你向池中扔了一块石头,结果显示点 $(x_p, y_p)$ 在池内(或边界上)。

请找到一条从起点到终点的路径,该路径由一系列线段组成,使得你永远不会穿过游泳池。

此图代表样例 1。所走的路径避开了隐藏的游泳池,但根据给出的信息,它也可能与游泳池相交。因此,样例解在这里相当幸运。

输入格式

第一行包含两个整数 $x_s$ 和 $y_s$ ($-10^4 \le x_s, y_s \le 10^4$)。 第二行包含两个整数 $x_t$ 和 $y_t$ ($-10^4 \le x_t, y_t \le 10^4$)。 第三行包含两个整数 $x_p$ 和 $y_p$ ($-10^4 \le x_p, y_p \le 10^4$)。

该问题是非自适应的,即对于每个测试用例,都存在四个整数 $x_l, y_l, x_r, y_r$ ($-10^4 \le x_l < x_r \le 10^4, -10^4 \le y_l < y_r \le 10^4$) 构成一个游泳池。起点和终点始终严格位于游泳池外部,且点 $(x_p, y_p)$ 位于池内(或边界上)。起点和终点始终不同。

输出格式

首先,输出一个整数 $N$ ($0 \le N \le 10$),表示你想要访问的起点和终点之间的点的数量。然后,输出 $N$ 行,第 $i$ 行包含两个整数 $x_i, y_i$。这些坐标必须满足 $-10^9 \le x_i, y_i \le 10^9$。注意,这些坐标的范围与其它坐标的范围不同。

这意味着你将沿着 $(x_s, y_s), (x_1, y_1), \dots, (x_N, y_N), (x_t, y_t)$ 之间的直线段行走,使得没有任何线段触碰到游泳池。可以证明解总是存在的。

样例

样例输入 1

0 0
4 4
2 2

样例输出 1

2
0 3
1 4

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.