GitHub 源文件 Markdown English

星际订单：交集分类

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

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。

背景故事

几何练习还需要进一步标注公共部分的形状。计算中心需要区分两个矩形的交集是一块区域、一条线段、一个点，还是空集。

形式化问题描述

给定平面上两个包含边界的闭矩形 \(A,B\) ，各边平行于坐标轴。每个矩形由任意顺序的一对对角端点确定，允许退化为线段或点。

按以下互斥情况对 \(A\cap B\) 分类：

1. 公共部分具有正面积，输出 Area .
2. 公共部分为长度大于零的线段，输出 Edge .
3. 公共部分恰好为一个点，输出 Point .
4. 没有公共点，输出 None .

Edge 包括线段完全位于另一个矩形内部的情形，不要求线段同时位于两个图形的外边界。两条线段交叉于一点时，应输出 Point .

实线表示 \(A\) ，虚线表示 \(B\) ；从左到右分别为 Area 、Edge 、Point 、None .

输入格式

第一行一个整数 \(T\) . 接下来 \(T\) 行，每行八个整数

x1 y1 x2 y2 x3 y3 x4 y4

前四个数给出 \(A\) 的两个对角端点，后四个数给出 \(B\) 的两个对角端点。

输出格式

输出 \(T\) 行，每行是 Area 、Edge 、Point 、None 之一。\(T=0\) 时输出为空。

样例

样例 1

输入

12
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

输出

None
Area
Point
Edge
Edge
Point
Area
Point
Edge
Edge
Area
Point

样例 2

输入

4
0 0 4 4 2 1 2 3
0 2 4 2 2 0 2 4
0 0 1 1 2 2 3 3
4 4 0 0 3 3 1 1

输出

Edge
Point
None
Area

样例 3

输入

0

输出

样例解释

样例 1 的第十组中，矩形覆盖 \([-5,-1]\times[-5,-1]\) ，另一图形是从 \((-2,-1)\) 到 \((-2,-2)\) 的线段。交集长度为 \(1\) ，所以输出 Edge .

样例 2 依次展示内部线段、线段交叉、不相交以及正面积包含。

数据范围与保证

对 100% 的数据：\(0\le T\le1000\) ，\(|x_i|,|y_i|\le10^9\) ，其中 \(1\le i\le4\) . 每个图形允许是正面积矩形、非零长度线段或点。下表中的“矩形”仅指正面积矩形，“线段”仅指非零长度线段。

分值比例	额外条件
40%	两个图形均为矩形
10%	两个图形均为线段
10%	两个图形均为点
10%	两个图形均为点或线段
10%	两个图形均为点或矩形
10%	两个图形均为线段或矩形
10%	无额外条件