#P15484. [CERC2012] The Dragon and the knights
[CERC2012] The Dragon and the knights
说明
瓦维尔城堡的巨龙在与当地鞋匠公会冲突后,决定将狩猎场迁出克拉科夫,前往一个不那么敌对的地区。如今,它给和平宁静的比特王国带来了浩劫与恐惧。
在比特王国中有 条河流,每条河流都沿着一条直线流淌(也就是说,你可以将王国视为被无限直线分割的欧几里得平面)。任意三条河流都不交于一点。这些河流将王国划分成若干 区域。
幸运的是,王国有 位英勇的骑士。他们各自驻守岗位,发誓保护自己的区域。王国因此永享安宁…… 果真如此吗?
众所周知,巨龙不会攻击至少有一名骑士在其中的区域。然而,骑士们以战场上的勇气闻名,而非智慧。他们或许忘记保护某些区域了。
给定王国的地图和骑士的位置,判断是否所有区域都受到了保护。
输入格式
输入的第一行包含测试用例的数量 。随后是每个测试用例的描述:
每个测试用例以一行包含河流数量 ()和骑士数量 ()开始。接下来 行描述河流。其中第 行包含三个空格分隔的整数 ,绝对值不超过 。这些整数是第 条河流所在直线的方程 的系数。之后有 行描述骑士的位置:第 行包含两个整数 ()——第 个骑士的坐标。你可以假设没有骑士站在河流中(若站在河中,他闪亮的盔甲会很快生锈)。两名骑士可能占据同一位置(他们的坐标可能相等)。没有两条河流沿同一条直线流淌,且任意三条河流都不交于一点。
输出格式
按照输入中出现的顺序输出每个测试用例的答案。对于每个测试用例,输出一行,如果所有区域都免受巨龙的威胁,则输出单词 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
京公网安备 11011102002149号