QOJ.ac

QOJ

Límite de tiempo: 8 s Límite de memoria: 1024 MB Puntuación total: 100

#14857. 相干性

Estadísticas

玩家通常会亲手为这些微缩模型上色。

现在是公元 40025 年 3 月 25 日,在《战斧玩家大对决 40,000》(Battle Axe Player Clash 40,000,简称 BAPC40K)的世界中。这款未来的桌面微缩模型战争游戏使用被称为“模型”(models)的可爱棋子进行,每个棋子都放置在一个圆形底座上。这些模型被放置在一个 $100\text{ km} \times 100\text{ km}$ 的游戏版图上。

如果在一组模型中,任意两个模型之间都存在一条未中断的模型链,且链中相邻两个模型的底座边缘之间的欧几里得距离最多为 2 英寸(1 英寸等于 25.4 毫米),则这组模型构成一个相干单位(coherent unit)。此外,如果该单位包含 7 个或更多模型,则每个模型必须与至少另外两个模型的底座边缘距离在 2 英寸以内。

给定一组具有不同底座直径的模型的位置,请判断它们是否构成一个单一的相干单位。

可以证明,对于本题的任何有效输入,如果圆形底座的直径与给定直径的偏差不超过 $10^{-5}\text{ mm}$,模型单位的相干性不会改变。

输入格式

输入包含:

  • 第一行包含一个整数 $n$($2 \le n \le 2 \cdot 10^5$),表示模型的数量。
  • 接下来的 $n$ 行,每行包含三个整数 $x$、$y$ 和 $d$($0 \le x, y \le 10^8$,$d \in \{25, 28, 32, 40, 50, 65, 80, 90, 100, 130, 160\}$),描述一个中心坐标为 $(x, y)$ 且底座直径为 $d$ 的模型,所有单位均为毫米。

每个模型(包括底座)都完全位于游戏版图内。

保证任意两个模型不会重叠,但模型可以接触。

输出格式

如果这 $n$ 个模型构成一个单一的相干单位,输出 yes。否则,输出 no

样例

输入样例 1

2
13 13 25
88 13 25

输出样例 1

yes

输入样例 2

2
13 13 25
89 13 25

输出样例 2

no

输入样例 3

7
1255 1120 65
1204 1226 160
1090 1252 65
998 1179 160
998 1061 65
1090 988 160
1204 1014 65

输出样例 3

no

输入样例 4

7
1066 910 130
1007 1032 130
875 1062 130
770 978 130
770 843 130
875 758 130
1007 788 130

输出样例 4

yes

图 C.1:样例示意图。样例 1 和样例 4 是相干的。样例 2 不是相干的,因为两个模型距离太远。样例 3 不是相干的,因为并非所有模型都与至少另外两个模型的距离在两英寸以内。

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.