星际订单：矩形相交¶
预估时间限制：0.5 秒。内存限制：128 MB。
实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
星际计算中心完成运动计算订单后，又收到了制作几何练习的任务。练习中的两个矩形有时会压扁成线段，甚至缩成一个点，需要判断它们是否仍有公共部分。
形式化问题描述¶
在平面直角坐标系中，给定两个闭矩形 \(A,B\) . 各边平行于坐标轴，每个矩形由一条对角线的两个端点确定，端点顺序任意。
矩形包含内部及边界。两个端点的某一维坐标相同时，矩形可以退化为线段；两维坐标都相同时退化为点。
判断 \(A\cap B\) 是否非空。只有一个公共点也算相交。
实线表示 \(A\) ，虚线表示 \(B\) . 前三组相交，第四组不相交；第二组中的线段完全位于矩形内部。
输入格式¶
第一行一个整数 \(T\) . 接下来 \(T\) 行，每行八个整数
x1 y1 x2 y2 x3 y3 x4 y4
前四个数是 \(A\) 的两个对角端点，后四个数是 \(B\) 的两个对角端点。
输出格式¶
每组输出一行：相交时输出 Intersection Found ，否则输出 Intersection Not Found . 字符串的大小写和空格必须一致。\(T=0\) 时输出为空。
样例¶
样例 1¶
输入¶
13
0 0 1 1 2 2 3 3
-1 2 2 -1 0 0 1 1
0 0 0 0 0 0 0 0
0 1 0 5 0 2 0 3
0 0 5 5 2 -5 3 0
0 0 5 0 2 -1 2 2
0 0 2 2 -1 -1 1 1
0 0 0 0 5 0 -1 0
-1 -1 -5 -5 -5 0 -5 -2
-1 -1 -5 -5 -2 -1 -2 -2
-2 1 2 -1 1 2 -1 -2
0 0 2 2 0 1 -1 1
0 0 0 0 1 1 1 1
输出¶
Intersection Not Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Not Found
样例 2¶
输入¶
4
0 0 4 4 2 1 2 3
0 2 4 2 2 0 2 4
1 1 1 1 2 2 2 2
-1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
输出¶
Intersection Found
Intersection Found
Intersection Not Found
Intersection Found
样例 3¶
输入¶
0
输出¶
样例解释¶
样例 1 包含不相交、包含、点重合、线段重合与边界接触。样例 2 的第一组是矩形包含线段，第二组是两条线段交于一点；它们都算相交。第四组在坐标上界处共用一个点。
数据范围与保证¶
对 100% 的数据：\(0\le T\le1000\) ，\(|x_i|,|y_i|\le10^9\) ，其中 \(1\le i\le4\) . 允许退化以及任意顺序的对角端点。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |