分数: 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
