eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Getting Through

Getting Through

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

A long and straight corridor is fitted with a number of sensors. Each sensor has a certain range within which it can detect objects or persons. If a part of an object is within the sensor’s range, an alarm will go off. Otherwise, nothing will happen.

Ethan needs to traverse this corridor in order to do some spy stuff at the other end. The question is, can he pass through the corridor without being detected? Can he fit so easily that he can bring some equipment along, or does he have to wear some tight clothing? Or can he perhaps sent a robot through instead?

We model the corridor as being two-dimensional (we ignore the height), bounded by two straight lines. Each sensor is located inside the corridor or on a wall. Their scopes are well in between the two ends of the corridor. We model the person or robot going through as a circle. Given the layout, what is the maximum radius this circle can have so that it is possible to negotiate the corridor without being detected?

A visual representation of the samples.

Входные данные

On the first line one positive number: the number of test cases, at most 100. After that per test case:

  • one line with a single integer w (1w100000): the width of the corridor. The two walls are given by the lines x = 0 and x = w.

  • one line with a single integer n (0n1000): the number of sensors in the corridor.

  • n lines with three space-separated integers x, y and r (0xw, -100000y100000 and 1r100000): the location and the range of each sensor, respectively.

The two ends of the corridor are at y = -1 and y = +1, or in less technical terms, they are far beyond the scope of all the sensors.

Выходные данные

Per test case:

  • one line with one floating point number: the radius of the largest circular object (or person) that could pass through the corridor without being detected, assuming the object can (be) move(d) with absolute precision. If nothing could possibly get through, the output should be zero.

The number should be accurate up to 10^{-6 }absolute precision.

Пример

Входные данные #1
3
10
2
2 0 3
7 12 4
10
2
2 0 3
7 8 4
10
2
2 0 3
7 4 4
Выходные данные #1
1.5
1.216991
0
Источник The 2013 Benelux Algorithm Programming Contest, BAPC 2013