#P15484. [CERC2012] The Dragon and the knights

[CERC2012] The Dragon and the knights

说明

瓦维尔城堡的巨龙在与当地鞋匠公会冲突后,决定将狩猎场迁出克拉科夫,前往一个不那么敌对的地区。如今,它给和平宁静的比特王国带来了浩劫与恐惧。

在比特王国中有 nn 条河流,每条河流都沿着一条直线流淌(也就是说,你可以将王国视为被无限直线分割的欧几里得平面)。任意三条河流都不交于一点。这些河流将王国划分成若干 区域

幸运的是,王国有 mm 位英勇的骑士。他们各自驻守岗位,发誓保护自己的区域。王国因此永享安宁…… 果真如此吗?

众所周知,巨龙不会攻击至少有一名骑士在其中的区域。然而,骑士们以战场上的勇气闻名,而非智慧。他们或许忘记保护某些区域了。

给定王国的地图和骑士的位置,判断是否所有区域都受到了保护。

输入格式

输入的第一行包含测试用例的数量 TT。随后是每个测试用例的描述:

每个测试用例以一行包含河流数量 nn1n1001\le n\le 100)和骑士数量 mm1m500001\le m\le 50000)开始。接下来 nn 行描述河流。其中第 jj 行包含三个空格分隔的整数 Aj,Bj,CjA_j, B_j, C_j,绝对值不超过 1000010000。这些整数是第 jj 条河流所在直线的方程 Ajx+Bjy+Cj=0A_j\cdot x + B_j\cdot y + C_j = 0 的系数。之后有 mm 行描述骑士的位置:第 ii 行包含两个整数 Xi,YiX_i, Y_i109Xi,Yi109−10^9\le X_i,Y_i\le 10^9)——第 ii 个骑士的坐标。你可以假设没有骑士站在河流中(若站在河中,他闪亮的盔甲会很快生锈)。两名骑士可能占据同一位置(他们的坐标可能相等)。没有两条河流沿同一条直线流淌,且任意三条河流都不交于一点。

输出格式

按照输入中出现的顺序输出每个测试用例的答案。对于每个测试用例,输出一行,如果所有区域都免受巨龙的威胁,则输出单词 PROTECTED,否则输出 VULNERABLE

2
3 7
0 1 0
1 0 0
1 1 -3
1 1
5 -1
3 2
2 -2
-2 6
-1 -2
-8 4
1 1
0 1 0
0 1
PROTECTED
VULNERABLE