QOJ.ac

QOJ

Time Limit: 1.0 s Memory Limit: 256 MB Total points: 100

#15914. 龙与骑士

Statistics

瓦维尔城堡的龙在与当地鞋匠协会发生冲突后,决定将其狩猎场迁出克拉科夫,前往一个不那么充满敌意的地方。现在,它正在给宁静祥和的字节王国带来浩劫与恐怖。

在字节王国中有 $n$ 条河流,每条河流都沿着一条直线流动(也就是说,你可以将王国视为被无限直线分割的欧几里得平面)。没有三条河流共点。这些河流将王国划分成了若干个区域。

幸运的是,王国里有 $m$ 位英勇的骑士。他们每人都坚守岗位,并宣誓保护自己所在的区域。王国因此得以永远受到保护……真的是这样吗?

众所周知,龙不会攻击至少有一名骑士驻守的区域。然而,这些骑士以战场上的勇气闻名,而非智谋。他们可能忘记了保护某些区域。

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

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述:

每个测试用例的第一行包含河流数量 $n$ ($1 \leqslant n \leqslant 100$) 和骑士数量 $m$ ($1 \leqslant m \leqslant 50\,000$)。接下来是 $n$ 行描述河流的直线。第 $j$ 行包含三个整数 $A_j, B_j, C_j$,其绝对值不超过 $10\,000$。这些整数是第 $j$ 条河流所在直线的方程 $A_j \cdot x + B_j \cdot y + C_j = 0$ 的系数。此后有 $m$ 行描述骑士的位置:第 $i$ 行包含两个整数 $X_i, Y_i$ ($-10^9 \leqslant X_i, Y_i \leqslant 10^9$),即第 $i$ 位骑士的坐标。你可以假设没有骑士站在河流上(否则他闪亮的盔甲会很快生锈)。两名骑士可能占据同一个位置(他们的坐标可以相同)。没有两条河流沿同一条直线流动,也没有三条河流共点。

输出格式

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

样例

输入 1

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

输出 1

PROTECTED
VULNERABLE

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.