시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB68383756.061%

문제

The Department of Defense has been designing autonomous robots that can infiltrate war zones and other hostile places in order to carry out missions. Now they want to test their latest design, the Penetrator1700, and they’ve hired you to help design the test environment.

The test environment is a rectangular field with some sensors placed within the field. Each sensor has a certain radius defining the region within which it can detect a robot. You want to design the field to have as many sensors as possible while still permitting a route across the field that avoids detection.

The field is a region of the coordinate plane defined by 0 ≤ x ≤ 200 and 0 ≤ y ≤ 300. The robot can be modeled by a point that must remain on the field at all times. It starts at the bottom of the field (y = 0) and must end at the top of the field (y = 300), and must not pass within range of any sensor. There are N sensor locations given by triples (x, y, r) of integers, where each (x, y) is a point on the field, and r is its radius of detection. The implied sensor circles may overlap, but will never be tangent with each other nor with the boundary of the field. All sensors are initially inactive. You must find the largest value of k such that if sensors 1, 2, 3, . . . , k are activated there is a path for the robot across the field, but no path if the (k+1)st sensor is also activated. It is guaranteed that there is no path if all N sensors are activated.

Figure K.1: Sensor circles corresponding to the first three sample inputs.

입력

Input begins with a positive integer N ≤ 200. Each of the next N lines has three space-separated integers, representing x, y, r for a sensor, where r ≤ 300. All sensors lie at different (x, y) positions. The first three sample inputs below correspond to the figure shown.

출력

Output a single integer (which may be 0) giving the largest k as described above.

예제 입력 1

6
36 228 58
164 224 58
88 170 42
93 105 42
167 85 58
28 44 58

예제 출력 1

2

예제 입력 2

6
36 228 58
28 44 58
164 224 58
88 170 42
93 105 42
167 85 58

예제 출력 2

3

예제 입력 3

6
28 44 58
36 228 58
88 170 42
93 105 42
164 224 58
167 85 58

예제 출력 3

4

예제 입력 4

3
100 150 101
30 30 10
170 30 100

예제 출력 4

0

출처

ICPC > Regionals > North America > North America Qualification Contest > ACM-ICPC North America Qualifier 2015 K번

  • 문제를 만든 사람: Robert Hochberg