После того, как вы получили 13 вердиктов time-limit-exceeded по ужасной геометрической задаче, вы решили сделать расслабляющий перерыв и позаниматься оригами.
Есть лист бумаги в форме простого многоугольника с \(n\) вершинами. Многоугольник может быть невыпуклым, но мы все знаем, что настоящий лист бумаги для оригами имеет свойство, что любая горизонтальная прямая пересекает границу многоугольника не больше, чем в двух точках.
Если вы согнете лист бумаги вдоль вертикальной прямой \(x=f\), какой будет площать полученной фигуры? Когда вы сгибаете лист, часть бумаги слева от прямой симметрично отражается с правой стороны.
Ваша задача ответить на \(q\) независимых запросов для значений \(f_1,\ldots,f_q\).
Выходные данные
Для каждого запроса выведите площадь \(A_i\) бумаги, которая будет, если согнуть лист бумаги вдоль прямой \(x=f_i\).
Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превосходит \(10^{-4}\).
Формально, пусть ваш ответ будет \(a\), а ответ жюри будет \(b\). Ваш ответ будет принят тогда и только тогда, когда \(\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}\).
Примечание
В первом тесте, если сделать сгиб в \(f=-5\):
Во втором тесте, если сделать сгиб в \(f=1\):
В третьем тесте, если сделать сгиб в \(f=-1\):
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 7
0 10
10 0
0 -10
-10 0
-9
-5
-1
0
1
5
9
|
199.0000000000
175.0000000000
119.0000000000
100.0000000000
119.0000000000
175.0000000000
199.0000000000
|
|
2
|
4 1
0 0
0 2
2 4
2 2
1
|
3.0000000000
|
|
3
|
9 4
0 -3
2 -2
-1 -1
0 4
2 5
1 6
-2 3
-1 1
-3 0
0
-2
-1
1
|
11.1250000000
11.7500000000
10.3446969697
11.3333333333
|