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

Asteroids collision

Asteroids collision

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

Даны два выпуклых многоугольника с числом вершин N и M, соответственно, а также два вектора, задающие их движение. Длина вектора определяет скорость в единицах длины в секунду. Ваша задача - выяснить, столкнуться ли эти многоугольники.

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

В первой строке содержится число вершин в первом многоугольнике N (3N, M40000. В следующих N строках содержаться координаты вершин, все координаты не превосходят по модулю 10^8.

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

Если ответ отрицательный, выведите "No solution", в противном случае выыведите время столкновения (касание считается столкновением) как несократимую дробь в виде x/y. Движение начинается в момент времени 0.

Пример

Входные данные #1
4
0 0
1 0
1 1
0 1
0 0
3
2 0
3 0
3 1
-1 0
Выходные данные #1
1/1
Источник Зимняя школа Харьков 2012, Контест* С.Пака