Выбрано 2 задачи 
Убрать все задачи
Заданы N-вершинный ориентированный граф с двумя выделенными вершинами
v1
и v2
и целое число C. Требуется:
1) определить, существует ли в заданном графе путь из вершины v1
в вершину v2, состоящий из C ребер (путь может иметь самопересечения как по
вершинам, так и по ребрам);
2) найти минимум функции |
X
-
C
|, где X – количество ребер в некотором пути из v1
в v2
.
Входные данные
Первая строка входного файла содержит целое число N – количество вершин в
графе (1 ≤ N ≤ 10). В следующих N строках расположена матрица
N × N из нулей и единиц, элемент (i, j) которой равен единице, если в графе есть ребро из
вершины i в вершину j, и нулю, если такого ребра нет. (Граф может содержать
петли, т.е. ребра, идущие из вершины в саму себя). Элементы матрицы во
входном файле записаны без разделительных пробелов.
Наконец, строка N+2 содержит номера вершин v1
и v2
, а строка N+3 – десятичную запись числа C (1 &le C <
1050).
Выходные данные
В первую строку выходного файла выведите ответ на первый пункт задачи:
«Yes», если путь длины C существует, и «No», если нет. Во вторую строку
запишите ответ на второй пункт задачи. Если ни одного пути из v1
в v2
не существует, ваша программа должна вывести -1.
Пример входного файла
3
010
001
100
1 1
555555555555555555555555555555555
Пример выходного файла
Yes
0
Нарисуйте многоугольник и точку на его границе так, что любая прямая, проходящая через эту точку, делит площадь этого многоугольника пополам.
|
|
 |
Условие
Нарисуйте многоугольник и точку на его границе так,
что любая прямая, проходящая через эту точку, делит площадь этого
многоугольника пополам.
Решение
Пусть нужная нам точка на границе многоугольника — O .
Построим сам многоугольник.
Разделим плоскость на 4 прямых угла с вершинами в точке O .
Построим равнобедренный прямоугольный треугольник AOB с вершиной в точке O
и катетами, лежащими на сторонах одного из прямых углов.
Построим равнобокую трапецию DEFG с боковыми сторонами DE=FG , лежащими на сторонах соседнего прямого угла, так, что OD=OG и площадь трапеции равна площади треугольника AOB .
Из условия равенства площадей
При этом D нужно выбрать в пределах отрезка OB ближе к точке D .
Аналогичным образом построим трапеции IJKL и MNPQ . Отрезки OA и QP при этом не должны пересекаться, что можно обеспечить соответствующим выбором расположений трапеций. На приведённом рисунке OA=OB=5 , OE=OF=6 , OJ=OK=7 и ON=OP=8 , в том, что OA и QP не пересекаются, а остальные соседние боковые стороны треугольника и трапеций, наоборот, частично совпадают, можно убедиться с помощью непосредственных вычислений.
Полученный многоугольник OABEFJKNPQMLIGD и точка O на его границе удовлетворяет условию задачи.
Покажем, что прямая XZ делит площадь нашего многоугольника на равные части. Площади трапеций DEFG и MNPQ , расположенных по разные стороны прямой XZ , равны по построению.
Эта прямая также делит в одинаковом соотношении площади треугольника OAB и трапеции IJKL (а поскольку площади этих фигур равны по построению, прямая делит каждую из них на части, площади которых соответственно равны площадям частей другой фигуры).
В самом деле, треугольники OAB и OJK подобны; кроме того, они равнобедренны, а прямая XZ проходит через вершину каждого из этих треугольников, образуя одинаковые углы с одной из боковых сторон, и, следовательно, делит их площади в одинаковом отношении. То же верно про треугольники OAB и OIL , поэтому прямая XZ делит их площади в том же отношении. Ну а площади частей трапеции IJKL равны разностям площадей соответствующих частей треугольников OJK и OIL .
Итак, мы видим, что по разные стороны от прямой XZ оказались части многоугольника соответственно равных площадей, поэтому суммарные площади также равны — прямая действительно делит площадь многоугольника пополам.
В случае, если прямая пересекает трапеции DEFG и MNPQ , доказательство строится аналогично. Случаи вертикального и горизонтального расположения секущей прямой являются тривиальными.
Как до такого решения можно догадаться? Фактически мы придумали два независимых решения, каждое — для своих двух вертикальных углов координатной плоскости. Причём одно из решений выбрали таким, чтобы нужная по условию задачи точка как раз была на его границе. А затем просто "подогнали края" — так, чтобы решения "цеплялись друг за друга" во всех местах, кроме одного.
