# 星际订单：矩形相交

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

星际计算中心完成运动计算订单后，又收到了制作几何练习的任务。练习中的两个矩形有时会压扁成线段，甚至缩成一个点，需要判断它们是否仍有公共部分。

## 形式化问题描述

在平面直角坐标系中，给定两个闭矩形 $A,B$ . 各边平行于坐标轴，每个矩形由一条对角线的两个端点确定，端点顺序任意。

矩形包含内部及边界。两个端点的某一维坐标相同时，矩形可以退化为线段；两维坐标都相同时退化为点。

判断 $A\cap B$ 是否非空。只有一个公共点也算相交。

![矩形、内部线段、交叉线段和分离图形的相交示例](assets/intersections.svg)

实线表示 $A$ ，虚线表示 $B$ . 前三组相交，第四组不相交；第二组中的线段完全位于矩形内部。

## 输入格式

第一行一个整数 $T$ . 接下来 $T$ 行，每行八个整数

```text
x1 y1 x2 y2 x3 y3 x4 y4
```

前四个数是 $A$ 的两个对角端点，后四个数是 $B$ 的两个对角端点。

## 输出格式

每组输出一行：相交时输出 `Intersection Found` ，否则输出 `Intersection Not Found` . 字符串的大小写和空格必须一致。$T=0$ 时输出为空。

## 样例

### 样例 1

### 输入

```text
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
```

### 输出

```text
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

### 输入

```text
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
```

### 输出

```text
Intersection Found
Intersection Found
Intersection Not Found
Intersection Found
```

### 样例 3

### 输入

```text
0
```

### 输出

```text

```

## 样例解释

样例 1 包含不相交、包含、点重合、线段重合与边界接触。样例 2 的第一组是矩形包含线段，第二组是两条线段交于一点；它们都算相交。第四组在坐标上界处共用一个点。

## 数据范围与保证

对 100% 的数据：$0\le T\le1000$ ，$|x_i|,|y_i|\le10^9$ ，其中 $1\le i\le4$ . 允许退化以及任意顺序的对角端点。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |