Задача B. Рыбы и сеть ≡

Автор:	А. Кленин		Ограничение времени:	2 сек
Входной файл:	input.txt		Ограничение памяти:	8 Мб
Выходной файл:	output.txt

Условие

Рыболовная сеть состоит из N треугольных ячеек, заданных координатами вершин (x, y), (u, v), (p, q). Сеть установлена поперёк реки и полностью её перегораживает.

Косяк из F рыб разной толщины желает проплыть сквозь сеть таким образом, чтобы ни одна рыба не попалась. Предположим, что i-ая рыба имеет в наибольшем поперечном сечении форму круга диаметра d_i. Рыба может проскочить через определённую ячейку сети в том случае, если окружность диаметром d_i целиком помещается в соотвествующем треугольнике. Касания сторон треугольника разрешены. В единицу времени через данную ячейку может проплыть не более одной рыбы.

Требуется найти минимальное время, за котороое все F рыб могут пройти сквозь сеть, или определить, что это невозможно.

Формат входного файла

Входной файл содержит число N, за которым следует N групп по 6 чисел x_i y_i u_i v_i p_i q_i — координаты вершин ячеек. Далее идёт число F, за которым следует F чисел d_i — диаметры поперечного сечения рыб. Все числа d_i — вещественные, все остальные числа — целые. Координаты ячеек описывают правильную сеть, т.е. стороны ячеек не пересекаются, каждая сторона, кроме внешних, принадлежит ровно двум ячейкам.

Формат выходного файла

В выходной файл следует вывести единственное целое число — минимальное время, или −1, если не все рыбы смогут проплыть сквозь сеть.

Ограничения

1 ≤ N, F ≤ 1000

0 ≤ x_i, y_i, u_i, v_i, p_i, q_i ≤ 1000

0 ≤ d_i ≤ 1000

Примеры тестов

№	Входной файл (input.txt)	Выходной файл (output.txt)
1	1 0 0 10 10 0 10 2 1 1 скопировать	2 скопировать

---