题目描述

尽管伟大的时空旅行者项少龙的故事未被历史记载，但近期的发现表明这位古代神秘访客可能真实存在。数月前，一些新出土的兵马俑旁发现了一台奇怪的机器，其外观甚至带有现代电子元件——这也让人们在猜测这台机器的起源时联想到了项少龙。

经过仔细研究，科学家们终于弄清了这台机器的用途——它实际上是秦朝的自动售货机！机器的面板上有一个孔洞，科学家们确信秦人通过这个孔洞投入钱币来购买物品。众所周知，秦朝之前存在多种不同类型的钱币，而秦始皇并不喜欢这种情况。但科学家们在机器上发现了秦始皇的诏令，声明任何能通过该孔洞的钱币仍可合法使用。现在，你的任务是判断某种钱币是否能被投入孔洞——我们或许能从中找到关于这位神秘时空旅行者的线索。

面板上的孔洞是一个多边形，所有钱币也是多边形（可能为凹多边形）。科学家发现古人使用这台售货机的方式如下：带孔洞的面板水平放置，顾客在孔洞上方选择一个最佳位置手持钱币，然后松手让钱币自由落下。在下落过程中，钱币不会发生任何方向的旋转。如果钱币能穿过孔洞，则视为“合法”（$legal$）；否则视为“非法”（$illegal$）。若钱币仅轻微触碰孔洞边缘但未被卡住，仍视为合法。例如，如样例输入所示，边长为$5$的正方形钱币能通过边长为$3$、$4$、$5$的三角形孔洞，因此是合法的。

注意：钱币和面板均被视为无厚度。

输入格式

第一行输入一个整数 $T$$（0 < T ≤ 20）$，表示测试用例数量。 每个测试用例的结构如下：

第一行输入一个整数 $N$$（3 ≤ N ≤ 20）$，表示孔洞多边形的顶点数。

接下来$N$ 行按逆时针顺序描述孔洞多边形的顶点坐标，每行包含两个实数 $r1$ 和$r2$$（-100 ≤ r1, r2 ≤ 100）$。

下一行输入一个整数 $M$$（3 ≤ M ≤ 20）$，表示钱币多边形的顶点数。

接下来 $M$ 行按逆时针顺序描述钱币多边形的顶点坐标，每行包含两个实数 $r1$ 和 $r2$$（-100 ≤ r1, r2 ≤ 100）$。

输出格式

对于每个测试用例，输出一行$“legal”$或$“illegal”$，表示钱币能否通过孔洞。

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

legal
legal

题目来源

2009年宁波程序设计竞赛