QOJ.ac

QOJ

Time Limit: 2.0 s Memory Limit: 512 MB Total points: 100 Hackable ✓

#16717. Judging the Trick

Statistics

Tricky Ricky 是一位世界闻名的魔术师。他甚至声称自己可以超越物理和几何定律。

在他最新的魔术中,他用完全包含在一个 $w \times h$ 矩形内的 $n$ 个三角形覆盖了该矩形。听起来很简单?但如果他告诉你这些三角形的总面积小于 $w \cdot h$,你会怎么说?

你是那种在派对和魔术表演中不太合群的人,所以你想向他证明这是不可能的。给定 $n$ 个三角形的描述,请在矩形中找到任意一个不属于任何三角形内部或边界的点。

输入格式

输入的第一行包含三个整数 $n$、$w$ 和 $h$($1 \le n \le 100\,000$,$1 \le w, h \le 10\,000$)—— 三角形的数量和矩形的尺寸。

接下来的 $n$ 行包含三角形顶点的描述。每行包含六个整数 $x_{i,1}$、$y_{i,1}$、$x_{i,2}$、$y_{i,2}$、$x_{i,3}$ 和 $y_{i,3}$($0 \le x_{i,j} \le w$,$0 \le y_{i,j} \le h$)。保证所有给定的三角形都是非退化的,且三角形的总面积小于 $w \cdot h$。

输出格式

输出两个实数 $x$ 和 $y$($0 \le x \le w$,$0 \le y \le h$),定义一个严格位于所有三角形之外的点的坐标。这些数字应以小数形式输出,小数点后最多保留 9 位数字。请注意,不允许使用科学计数法(指数格式)。如果给定的点不属于任何三角形的内部或边界,则您的答案将被视为正确。请注意,您的答案在验证时不会有任何绝对或相对误差容限。

保证(由欧几里得和其他一些人证明)这样的点总是存在。

样例

输入样例 1

5 4 3
0 0 3 0 0 2
3 3 0 1 0 3
1 1 3 1 2 3
3 0 4 0 4 3
4 3 3 2 4 1

输出样例 1

1.1 1.6

说明

样例的图示如下。

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.