|
Название задачи: Сократи векторы. |
 |
Условие
Максимальное время работы на одном тесте: 1 секунда
На плоскости задано N векторов - направленных отрезков, для каждого из которых известны координаты начала и конца (вектор, у которого начало и конец совпадают, называется нуль-вектором, можно считать, что нуль-вектор лежит на любой прямой, которая через него проходит). Введем следующие три операции над направленными отрезками на плоскости:
1) Направленные отрезки ненулевой длины, лежащие на пересекающихся прямых, можно заменить на их сумму, причем единственным образом. В этом случае отрезки переносятся вдоль своих прямых так, чтобы их начала совпадали с точкой пересечения прямых, и складываются по правилу сложения векторов (правилу параллелограмма, при этом началом результирующего вектора является точка пересечения прямых):
2) Направленные отрезки, лежащие на одной прямой, также можно заменить на их сумму. Для этого один из отрезков (любой) нужно перенести в начало второго из них и сложить по правилу сложения векторов на прямой:
Это правило применимо и в случае, когда один из векторов, или даже оба, являются нуль-векторами.
Заметим, что если складываемые векторы противоположно направлены и имеют одну и ту же длину, то результатом их сложения является нуль-вектор.
3) В любой точке плоскости можно породить два противоположно направленных отрезка равной (в том числе и нулевой) длины:
Будем говорить, что некоторая система векторов B эквивалентна системе A, если от системы A можно перейти к B с помощью конечной последовательности перечисленных выше операций.
Требуется получить любую систему векторов, эквивалентную заданной, состоящую из минимально возможного числа векторов.
Формат входных данных
В первой строке входного файла f.in записано число N - количество заданных векторов (1 < N ≤ 1000). В каждой из следующих N строк через пробел записаны четыре числа, обозначающие координаты начала и конца каждого из векторов соответственно. Все координаты - целые числа, по модулю не превосходящие 1000.
Формат выходных данных
В первой строке входного файла f.out следует записать число M - количество векторов в полученной системе (1 ≤ M ≤ N). В каждой из следующих M строк через пробел должны находиться четыре числа, обозначающие координаты начала и конца каждого из векторов соответственно. Все координаты - вещественные числа, записанные с 6 цифрами после точки.
Примеры
|
f.in |
f.out |
|
3 1 1 1 3 3 3 3 1 5 1 7 1 |
1 3.000000 3.000000 5.000000 3.000000 |
|
2 2 4 5 10 -2 -4 -5 -10 |
1 2.000000 4.000000 2.000000 4.000000 |
Также доступны документы в формате DOC
Решение
Тесты и проверяющая программаБудем исходить из физического смысла задачи. Если интерпретировать заданные векторы как силы, приложенные к твердому телу, то ответом должен быть минимальный набор сил, действующий на тело так же, как исходная система. При этом не должна измениться векторная сумма всех сил (это равнодействующая сил) и суммарный момент сил относительно произвольно выбранной точки (например, начала координат).
Пусть на плоскости заданы точка О и вектор a =
, d - расстояние от O до прямой AB. Моментом вектора a относительно точки O называется величина d×
|a|, взятая со знаком "плюс", если угол между лучами OA и AB положительный (т.е. вектор OA поворотом против часовой стрелки на угол, меньший 180╟, можно преобразовать в вектор, сонаправленный с
), "минус" в противном случае. Эта величина равна ориентированной площади [
,
] параллелограмма, построенного на векторах
и
(рис. 1) и в геометрии называется косым произведением векторов. Если
= (x1, y1),
= (x2, y2), то [
,
] = x1×
y2 - y1×
x2. Моментом системы относительно точки O называется сумма моментов всех векторов относительно O. Далее словом момент мы обозначаем момент относительно точки O. Операции над векторами, описанные в условии задачи, назовем элементарными. Всякие два вектора, лежащие на различных параллельных прямых, направленных противоположно и равных по длине, будем называть векторной парой (или парой, если из контекста ясно, что речь идет о векторной паре).
Получаем следующий способ решения задачи. Фиксируем произвольную точку O и для заданных векторов считаем их сумму и суммарный момент M относительно точки O. Если сумма векторов отлична от нуля, ответом будет вектор v, равный этой сумме. Линия действия этого вектора подбирается таким образом, чтобы момент вектора v относительно точки O был равен M. Один из способов найти начало A вектора v - из двух условий:
(, v) = x×
vx + y×
vy = 0 и [
, v] = x×
vy - y×
vx = M.
Здесь = (x, y) - искомый вектор, v = (vx, vy) - вектор суммы исходной системы.
Если сумма векторов равна нулю, а M ≠ 0, одним вектором в ответе, очевидно, обойтись нельзя. В этом случае достаточно отыскать пару противоположно направленных векторов одинаковой (например, единичной) длины, каждый из которых имеет момент M / 2 относительно точки O. Наконец, если и сумма векторов, и их суммарный момент нулевые, ответом будет нуль-вектор, приложенный к любой точке плоскости. Дадим обоснование этого способа решения.
Утверждение 1. Всякий вектор можно заменить равным ему вектором
, если точки A, B и C лежат на одной прямой.
Для этого нужно на прямой АВ породить два вектора и
' = -
, сложить
' и
и суммарный нуль-вектор прибавить к
, получив вектор с началом C. То есть любой вектор можно переносить вдоль линии его действия. Как следствие, нуль-вектор можно переносить в любую точку плоскости.
Утверждение 2. Элементарные операции сохраняют сумму векторов и момент системы относительно любой точки O.
Это утверждение очевидно для суммы векторов. Для моментов это свойство линейности: [,
] + [
,
] = [
,
+
], которое вытекает из координатной записи косого произведения векторов.
Утверждение 3. Любая конечная система векторов эквивалентна одному вектору или векторной паре.
Будем элементарными операциями сокращать количество векторов. Если имеются два непараллельных вектора или два вектора на одной прямой, их можно заменить на один. Если есть два коллинеарных вектора
и
разной длины, породим, например на прямой AC, две пары равных по длине векторов (рис. 2). Векторы
'' и
' в сумме дают нуль-вектор
. Суммируя векторы
' и
,
'' и
, получим два неколлинеарных вектора
и
. Их неколлинеарность следует из сохранения суммы векторов (если бы
и
оказались, то неколлинеарными были бы
+
и
+
, что противоречит утверждению 2. Затем складываем векторы
,
и
, получая один результирующий вектор. Так же можно поступить и с сонаправленными векторами одной длины. Таким образом, количество векторов можно уменьшать до тех пор, пока не останется один вектор (возможно, это нуль-вектор), либо два противоположно направленных вектора одной длины с разными линиями действия, т.е. векторная пара.
Из Утверждений 2 и 3 вытекает, что тип ответа (нуль-вектор, вектор или векторная пара) однозначно определяется суммарными вектором и моментом исходной системы. Остается показать, что любой ответ, для которого эти величины "правильные", может быть получен из исходной системы посредством элементарных преобразований. Рассмотрим разные типы ответа. Нуль-вектор, он и в Африке нуль-вектор (Утверждение 1). Второй случай: ответом является один ненулевой вектор v = . Если другой вектор v1 =
с ним сонаправлен, имеет те же длину и момент, то линии действия векторов v и v1 совпадают. Значит, по Утверждению 1 от v можно перейти к v1. Остается рассмотреть случай, когда ответом является векторная пара.
Утверждение 4. Две векторные пары, имеющие одинаковые моменты, эквивалентны.
Пусть у нас есть две векторные пары u, u' = -u и v, v' = -v с одинаковым моментом M, причем эти пары не параллельны. Покажем, что от пары u, u' можно перейти к паре v, v'. Будем считать (а можем так считать по Утверждению 1), что вектор u имеет началом точку A пересечения прямых, на которых лежат u и v, вектор u' - точку A' пересечения прямых, на которых лежат u'и v' (рис. 3). Породим на прямой AA' такие два вектора
и
= -
, чтобы вектор v1 =
+ u был параллелен вектору v. Это всегда возможно, поскольку u, v и
' попарно не параллельны. Векторы v1 и v1' =
+ u' образуют пару (они имеют сумму 0 и суммарный момент M), при этом векторы v1 и v лежат на одной прямой (как и векторы v' и v1'). Значит, v1 = k×
v, v'1 = k×
v'. Момент этой пары равен M = [
, v1] + [
', v'1] = k×
[
, v] + k×
[
', v'] = k×
M. Отсюда k = 1, v1 = v, v'1 = v'. Мы установили, что пары u, u' и v, v' эквивалентны, что и требовалось.
Если же все векторы u, u', v и v' параллельны, то сначала переведем указанным способом пару u, u' в любую пару, ей не параллельную, а затем из этой вспомогательной пары получим пару v, v'.
Итак, в приведенной задаче сразу можно было выписать ответ, исходя из простых физических соображений. Конечно, задачу можно решать и "в лоб", применяя цепочку элементарных преобразований. Порядок сокращения при этом не важен. Этот способ по сути описан при доказательстве утверждения 3. Участники олимпиады, решившие задачу на полный балл, поступали именно таким образом. Но и при таком решении полезно понимать физическую подоплеку задачи, это поможет найти правильный путь к цели.
Также доступны документы в формате DOC
