e-olymp 12. Поврежденная картина

Задача

Римская цифра [latex]I[/latex], стоявшая на полу комнаты в точке с координатами [latex]X_0[/latex], [latex]Y_0[/latex], [latex]0[/latex] не выдержала отношения к решению задачи «Римские цифры» и упала на пол. Поскольку нижний конец был прикреплен шарнирно, то он остался на месте, а верхний оказался в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], [latex]0[/latex]. В комнате стояла строго вертикально бумажная картина. Зная координаты концов нижнего основания [latex]X_2[/latex], [latex]Y_2[/latex], [latex]0[/latex] и [latex]X_3[/latex], [latex]Y_3[/latex], [latex]0[/latex] и высоту картины [latex]H[/latex] найти длину «разрыва бумаги» на картине.

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

Во входной строке записано 9 чисел [latex]X_0, Y_0, X_1, Y_1, X_2, Y_2, X_3, Y_3, H[/latex]. Все входные данные — целые числа, модуль которых не превышает [latex]10^9[/latex].

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

Программа выводит единственное число – искомую величину с точностью до [latex]0.001[/latex].

Тесты

Входные данные Выходные данные
1 1 6 1 4 0 4 5 6 4.000
0 0 6 0 2 0 5 0 5 2.397
2 0 5 0 0 0 6 0 5 4.172
0 0 5 0 2 0 6 0 1 2.058
0 0 10 0 2 0 6 0 1 0.000

Решение задачи

Эта задача интересна тем, что для ее решения необходимо смоделировать большое количество разнообразных взаиморасположений картины и буквы. Далее  будут использоваться следующие обозначения: [latex]X_0[/latex]- основание буквы, [latex]X_1[/latex] — ее вершины, [latex]X_2[/latex] и [latex]X_3[/latex] — координаты основания картины, [latex]Н[/latex] — высота картины.

1. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] лежат на одной прямой

1.1. [latex]X_0[/latex] принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1. [latex]X_1[/latex]принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1.1 [latex]X_0[/latex][latex]X_1[/latex] не превышает [latex]Н[/latex]

В таком случае искомая величина — дуга [latex]O X1[/latex], равная [latex]\frac{1}{4} [/latex] длины окружности с радиусом, равным высоте буквы: [latex]O[/latex][latex]X_1[/latex] = [latex]\frac{П\times X_0 X_1}{2} [/latex]

 

1.1.1.2 [latex]X_0[/latex][latex]X_1[/latex] больше, чем [latex]Н[/latex]

в таком случае нам необходимо найти дугу [latex]PB[/latex],для этого умножив радиус на величину центрального угла: [latex]PB[/latex] =[latex]X_0 X_1 \times arcsin \frac{X_0 X_1}{H}[/latex]

1.1.2 [latex]X_1[/latex] не принадлежит [latex]X_2 X_3[/latex]

1.1.2.1 [latex]X_2[/latex] принадлежит [latex]X_0 X_1[/latex]

1.1.2.1.1 [latex]X_0 X_1[/latex] не превышает [latex]H[/latex]

В таком случае нам нужно найти дугу [latex]OM[/latex] по схожему с случаем 1.1.1.2 алгоритму: [latex]OM[/latex] = [latex]X_0 X_1 \times arcsin \frac{X_0 X_2} {X_0 X_1} [/latex]

 

1.1.2.1.2 [latex]X_0[/latex][latex]X_1[/latex] больше [latex]H[/latex]

В таком случае искомая величина равна дуге1 [latex]MN[/latex]= [latex]X_0 X_1 \times  arcsin \frac{H}{X_0 X_1} — arccos \frac{X_0 X_2}  {X_0 X_1}[/latex])

1.1.2 [latex]X_3[/latex] принадлежит [latex]X_0 X_1[/latex]

Данный случай аналогичен предыдущему. Единственное отличие заключается в том, что в формулах необходимо заменить [latex]X_0[/latex][latex]X_2[/latex] на [latex]X_0[/latex][latex]X_3[/latex]

1.2 [latex]Х_1[/latex] принадлежит [latex]X_2[/latex][latex]X_3[/latex]

введем новую переменную [latex]A[/latex], равную расстоянию от [latex]X_0[/latex] до картины.

1.2.1 [latex]X_0 X_1[/latex] меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

В данном случае нам нужно найти дугу [latex]M X_1[/latex] = [latex]X_0 X_1 \times arccos \frac{A}{X_0 X_1}[/latex]

1.2.2 [latex]X_0[/latex][latex]X_1[/latex] не меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

в этом случае нам нужно найти дугу [latex]МХ_1[/latex]= [latex]X_0 X_1 \times arсsin \frac{A}{X_0 X_1}[/latex]

 

1.3 обе вершины цифры не принадлежат картине

Обозначим через [latex]A[/latex] расстояние от [latex]X_0[/latex] до дальней вершины картины.

1.3.1 [latex]X_0 X_1 < \sqrt{A^2 + H^2} [/latex]

Искомая величина — дуга [latex]MN[/latex] = [latex]X_0 X_1\times  arcsin \frac{H}{X_0 X_1}  —  arccos \frac{A}{X_0 X_1}[/latex]

2. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] не лежат на одной прямой

2.1. [latex]X_0 X_1[/latex] пересекает [latex]X_2 X_3[/latex]

В этом случае длина разрыва будет равна длине отрезка [latex]MN[/latex] либо высоте картины, если она окажется меньше вышеупомянутого отрезка.

Для того, чтобы не рассматривать случаи, в которых искомая величина равна нулю(все оставшиеся), при создании переменной, в которой будем хранить ответ, сразу приравняем ее к нулю.

Ссылки

Условие задачи на сайте e-olymp
код к задаче

Добавить комментарий