Задача №113890. Фото от пилота
Дима архитектор. А ещё Дима фотограф. Он часто носится по свету и фотографирует местные Биг Бены и прочие крутые сооружения.
На этот раз Дима приехал в Берляндию, знаменитую своим метрополитеном. Он состоит из n линий, каждая из которых представлена прямой на карте города. На пересечении каждых двух линий метрополитена расположены станции, наземные павильоны которых признаны национальными памятниками архитектуры. Как только Дима увидел их с экрана своего смартфона, он мгновенно загорелся желанием их сфотографировать.
Специально для этой цели он решил воспользоваться маршрутным вертолётом, с которого планирует осуществлять съёмку. Вертолёты компании летают по t маршрутам. Каждый маршрут представляет собой прямую линию. Дима может сделать фотографию, находясь в любой точке маршрута, однако, чем меньше расстояние до станции, тем больше деталей будет видно на снимке, и он соберёт больше лайков в социальных сетях. Вот тут Диме нужна ваша помощь.
Вам даны n прямых, задающих линии метро, и t прямых, задающих доступные вертолётные маршруты. Дима просит для каждого маршрута найти расстояние до ближайшей к нему станции.
Гарантируется, что никакие две линии метрополитена не совпадают и что любые две линии пересекаются, а также, что любые два маршрута пересекаются и что любой маршрут пересекается с любой линией.
В первой строке входного файла находятся два числа n и t ( 2 ≤ n ≤ 100 000 , 1 ≤ t ≤ 20 ) — количество линий метро и количество возможных маршрутов, соответственно.
В следующих n строках содержатся по три целых числа a i , b i и c i ( | a i |, | b i | ≤ 10 000 , a i 2 + b i 2 > 0 , | c i | ≤ 10 8 ), описывающие линии метро. Каждая линия представляет собой прямую a i · x + b i · y + c i = 0 .
Затем следуют t строк с описанием возможных вертолётных маршрутов, каждая из них содержит три целых числа u i , v i , w i ( | u i |, | v i | ≤ 10 000 , u i 2 + v i 2 > 0 , | w i | ≤ 10 8 ). Аналогично, каждый маршрут представляет собой прямую u i · x + v i · y + w i = 0 .
Для каждого маршрута выведите единственное вещественное число — расстояние между
i
-м вертолётным маршрутом и наиболее близкой к нему станцией. Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность относительно ответа жюри не будет превосходить
10
- 9
, то есть,
, где
p
— ответ участника, а
j
— ответ жюри.
Тесты по данной задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп кроме, возможно, тестов из условия.
Изображения к тестами из условия приведены ниже.
3 1 1 -1 0 1 1 -4 4 -6 -4 0 1 0
1.20000000000000000000
3 3 1 3 -6 -1 1 0 -5 2 15 3 -2 -3 -1 -1 4 1 0 -5
0.41602514716892186000 0.16637806616154061000 0.00000000000000000000