시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 2048 MB128866.667%

문제

It is the 25th of March, 40025 CE in the world of Battle Axe Player Clash 40,000 (BAPC40K). This futuristic table-top miniatures wargame is played with endearing figurines called models, each of which is placed on a circular base. The models are placed on a $100\,\text{km} \times 100\,\text{km}$ gaming board. A collection of such models forms a coherent unit if between any pair of models there is an unbroken chain of models that have a Euclidean distance of at most two inches1 between the edges of their bases. Moreover, if the unit contains seven models or more, each model must be within two inches of at least two other models. Given the positions of a collection of models with varying base diameters, determine whether they form a single coherent unit.

One can prove that for any valid input for this problem, if the diameters of the circular bases differ from the given diameter by at most $10^{-5}\,\text{mm}$, the coherency of a unit of models does not change.


1Recall that an inch equals $25.4\,\text{mm}$.

입력

The input consists of:

  • One line with an integer $n$ ($2\leq n \leq 2\cdot 10^5$), the number of models.
  • $n$ lines, each with three integers $x$, $y$, and $d$ ($0 \leq x, y \leq 10^8$, $d\in\{25, 28, 32, 40, 50, 65, 80, 90, 100, 130, 160\}$), describing a model that has its center coordinates at $(x,y)$ and a base diameter of $d$, all given in millimeters.

Each model (including the base) fits on the gaming board.

It is guaranteed that no two models are overlapping, but the models can touch.

출력

If the $n$ models form a single coherent unit, output "yes". Otherwise, output "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

노트

Figure C.1: Illustration of the samples. Samples 1 and 4 are coherent. Sample 2 is not coherent, because the two models are too far away. Sample 3 is not coherent, because not all models are within two inches of two other models.

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2025 C번

  • 문제를 만든 사람: Thore Husfeldt