Под легким прохладным бризом на воде появляется рябь.— Вода приходит и уходит, но не исчезает насовсем. Луна убывает и прибывает, но остается того же размера.
— Все приходящее. Все также вечно.
Канно не видит большого смысла в словах Мино, но, наверное, сейчас стоит просто насладиться легким бризом и ночным небом — неиссякаемыми дарами природы.
Глядя в звездное небо, Канно погружается в спокойный сон.
На плоскости отмечено множество \(S\) из \(n\) точек.
Канно начинает из некоторой точки плоскости \(P\), которою может выбрать самостоятельно. \(P\) не добавляется в \(S\), если, конечно, изначально не принадлежит \(S\). Затем следующая последовательность операций (вместе называющихся шагом) повторяется несколько раз:
- Выбирается прямая \(l\) такая, что она проходит через как минимум две точки из \(S\) и через текущую позицию Канно. Если таких прямых несколько, из них с равной вероятностью выбирается одна.
- Канно переходит в одну из точек из множества \(S\) на прямой \(l\). Точка назначения выбирается равновероятно из всех возможных, включая текущую позицию Канно, если она, конечно, принадлежит \(S\).
Вам даны \(q\) запросов, каждый из них состоит из двух целых чисел \((t_i, m_i)\). Для каждого запроса выведите максимально возможную вероятность для Канно оказаться в \(t_i\)-й точке множества \(S\) после \(m_i\) шагов при выборе оптимальной стартовой точки \(P\). Обратите внимание, в соответствии с правилом 1 \(P\) должна принадлежать как минимум одной прямой, которая проходит через две точки из \(S\).
Выходные данные
Выведите \(q\) строк, каждая из которых содержит одно вещественное число. \(i\)-е из этих чисел должно быть равно максимально возможной вероятности оказаться в точке \(t_i\) после \(m_i\) шагов при оптимальном выборе начальной точки \(P\).
Ваш ответ будет считаться правильным, если каждое из чисел, выведенных вами, отличается от ответа жюри не более чем на \(10^{-6}\).
Формально, пусть ваш ответ равен \(a\), а ответ жюри равен \(b\). Ваш ответ будет зачтен, если \(|a - b| \le 10^{-6}\).
Примечание
Точки множества \(S\) и все возможные прямые \(l\) показаны на рисунке ниже.
В первом примере если выбрать точку \(P = (-1, -3)\), то в качестве \(l\) будет обязательно выбрана точка \(3x = y\), поэтому Канно переместится в \((0, 0)\) с вероятностью \(\frac 1 2\).
В третьем запросе если выбрать точку \(P = (2, 2)\), то \(l\) будет выбрана с равной вероятностью между \(x + y = 4\) и \(x = y\). Тогда Канно переместится в остальные четыре точки с вероятностью \(\frac 1 2 \cdot \frac 1 3 = \frac 1 6\) для каждой точки, и останется в \((2, 2)\) с вероятностью \(\frac 1 3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
0 0
1 3
2 2
3 1
4 4
10
1 1
2 1
3 1
4 1
5 1
3 2
3 3
3 4
3 5
3 6
|
0.50000000000000000000
0.50000000000000000000
0.33333333333333331483
0.50000000000000000000
0.50000000000000000000
0.18518518518518517491
0.15226337448559670862
0.14494741655235482414
0.14332164812274550414
0.14296036624949901017
|