1495: 士兵突击问题

在一次的战役中，我军被敌人十万大军团团包围。为了寻求援军，我军派出

一名勇敢的战士，突围而出。由于地势险要，援军决定派出空降部队进行支援，

由于地面已被敌人设下了多个埋伏圈，我军选择空降地点至关重要。根据情报显

示，敌军的埋伏圈组成了多个不规则的多边形，我军必须迅速判断出降落地点是

否安全。

根据军事情报，我军将地图建立成一个平面直角坐标系，敌人的埋伏圈在地

图上构成了n 个不规则的多边形。我军的降落点是（x，y），请编程确定我军的

降落点（x，y）是否在敌人的埋伏圈之内。

第一行一个整数 T，表示测试数据的组数。对于每组测试数据，第一行有2

个数字x，y，表示我军的降落点，第二行是一个整数n，表示敌军的埋伏圈的个

数，接下来有n 行，每行表示一个埋伏圈。多边形埋伏圈的输入格式是每行的第

一个数是k，表示该多边形的定点个数，接下来按顺时针或逆时针顺序给出多边

形的顶点坐标x1 y1 x2 y2 … xk yk。其中，1<=T, n <=100, 3<=k<=100 所有坐标为

浮点数，x，y 方向上绝对值坐标小于10000。

对于每组测试数据输出一行“Safe”表示我军的降落地点是安全的，“Danger”

表示我军的降落地点在敌人的埋伏圈以内。注意，我军的降落点距离敌人的埋伏

圈小于10-6，我们认为是危险的。

2
1.0 2.0
2
4 0 0 0 2 2 2 2 0
3 2 2 4 2 4 4
1.0 2.5
2
4 0 0 0 2 2 2 2 0
3 2 2 4 2 4 4

Danger
Safe