← 返回题目列表

AtCoder · jag2018summer_day2_g

G. 构造一个点

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

你有 Q 三角形,编号 1 通过 Q.

的顶点坐标 i第一个三角形是 (x_{i1}, y_{i1}), (x_{i2}, y_{i2}) 和 (x_{i3}, y_{i3}) 按逆时针顺序。 在这里, x_{i1}, x_{i2}, x_{i3}, y_{i1}, y_{i2} 和 y_{i3} 均为整数。

对于每个三角形,判断其内部(不包括边界)是否存在包含网格点。如果存在,则构造一个这样的点。

约束

  • 所有输入值均为整数。
  • 1 \leq Q \leq 10 000
  • 0 \leq x_{i1}, x_{i2}, x_{i3}, y_{i1}, y_{i2}, y_{i3} \leq 10^9
  • (x_{i1}, y_{i1}), (x_{i2}, y_{i2}) 和 (x_{i3}, y_{i3}) 按逆时针顺序排列。
  • 三角形的面积不是 0.

输入

输入由标准输入按以下格式给出:

Q
x_{11} y_{11} x_{12} y_{12} x_{13} y_{13}
x_{21} y_{21} x_{22} y_{22} x_{23} y_{23}
:
x_{Q1} y_{Q1} x_{Q2} y_{Q2} x_{Q3} y_{Q3}

输出

输出应包含 Q 行。

在 i第行,如果网格内部(不包括边界)包含网格点 i第一个三角形,打印 -1 -1。 如果存在,选择一个这样的网格点,然后打印它 x- 坐标和 y- 坐标之间有一个空格。


示例输入 1

4
1 7 3 5 5 7
1 4 1 2 5 4
6 1 7 1 7 6
11 3 11 4 8 5

示例输出 1

3 6
2 3
-1 -1
10 4