AT_abc168_f [ABC168F] . (Single Dot)

题目描述

有一片无限广阔的草原。

在这片草原上，有一头体积可以忽略不计的小牛。以牛当前位置为原点，从该点向南移动 $x\ \mathrm{cm}$、向东移动 $y\ \mathrm{cm}$ 后的位置记作 $(x,\ y)$。牛当前所在的位置为 $(0,\ 0)$。

此外，草原上画有 $N$ 条竖直线段和 $M$ 条水平线段。第 $i$ 条竖直线段连接点 $(A_i,\ C_i)$ 和点 $(B_i,\ C_i)$，第 $j$ 条水平线段连接点 $(D_j,\ E_j)$ 和点 $(D_j,\ F_j)$。

只要牛不经过任何线段（包括端点），它就可以在草原上自由移动。请问牛能够活动的区域面积是多少 $\mathrm{cm^2}$？如果该区域面积为无穷大，则输出 INF。

输入格式

输入以如下格式从标准输入给出。

$N$ $M$ $A_1$ $B_1$ $C_1$ $:$ $A_N$ $B_N$ $C_N$ $D_1$ $E_1$ $F_1$ $:$ $D_M$ $E_M$ $F_M$

输出格式

如果牛能够活动的区域面积为无穷大，则输出 INF，否则输出该面积的整数值（单位：$\mathrm{cm^2}$）。

（在本题的约束下，如果牛能够活动的区域面积是有限的，那么该面积一定是整数。）

输入输出样例 #1

输入 #1

5 6
1 2 0
0 1 1
0 2 2
-3 4 -1
-2 6 3
1 0 1
0 1 2
2 0 2
-1 -4 5
3 -2 4
1 2 4

输出 #1

13

输入输出样例 #2

输入 #2

6 1
-3 -1 -2
-3 -1 1
-2 -1 2
1 4 -2
1 4 -1
1 4 1
3 1 4

输出 #2

INF

说明/提示

约束

• 所有输入均为 $-10^9$ 以上 $10^9$ 以下的整数
• $1\leq N, M \leq 1000$
• $A_i < B_i\ (1\leq i\leq N)$
• $E_j < F_j\ (1\leq j\leq M)$
• 点 $(0, 0)$ 不在任何给定的线段上

样例解释 1

牛能够活动的区域面积为 $13\ \mathrm{cm^2}$。

样例解释 2

牛能够活动的区域面积为无穷大。

由 ChatGPT 4.1 翻译