Выбрано 2 задачи 
Убрать все задачи
Максимальное время работы на одном тесте: 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 |
Дана таблица n×n клеток и такие натуральные числа k и m > k, что m и n – k взаимно просты. Таблица заполняется следующим образом: пусть в некоторой строчке записаны числа a1, ..., ak, ak+1, ..., am, am+1, ..., an. Тогда в следующей строчке записываются те же числа, но в таком порядке: am+1, ..., an, ak+1, ..., am, a1, ..., ak. В первую строчку записываются (по порядку) числа 1, 2, ..., n. Доказать, что после заполнения таблицы в каждом столбце будут написаны все числа от 1 до n.
|
|
 |
Условие
Дана таблица n×n клеток и такие натуральные числа k и m > k, что m и n – k взаимно просты. Таблица заполняется следующим образом: пусть в некоторой строчке записаны числа a1, ..., ak, ak+1, ..., am, am+1, ..., an. Тогда в следующей строчке записываются те же числа, но в таком порядке: am+1, ..., an, ak+1, ..., am, a1, ..., ak. В первую строчку записываются (по порядку) числа 1, 2, ..., n. Доказать, что после заполнения таблицы в каждом столбце будут написаны все числа от 1 до n.
Решение
Очевидно достаточно доказать, что ни одно из чисел не вернётся на свое место во 2-й, 3-й, ... , n-й строках. Проследим за судьбой какого-нибудь числа a. При переходе в следующую строку оно сдвигается вправо на одно из (положительных или отрицательных) чисел s = n – k, s – m = n – m – k, – m. Пусть после нескольких шагов оно x раз побывало в первой группе (на одном из мест от 1 до k), y раз – во второй, z раз – в третьей и при этом впервые вернулось на исходное место. Тогда sx + (s – m)y – mz = 0, 0 ≤ x ≤ k, 0 ≤ y ≤ m – k, 0 ≤ z ≤ n – m.
Обозначим s = n – k. Наше уравнение можно переписать в виде s(x + y) = m(y + z). Так как m и s взаимно просты по условию, то x + y делится на m и y + z делится на s. Но 0 ≤ x + y ≤ m и 0 ≤ y + z ≤ s, откуда либо x = y = z = 0, либо x = n – s, y = m + s – n, z = n – m. Первый случай нас не интересует, а во втором случае x + y + z = n, то есть число a возвращается на свое место в (n+1)-й строке, то есть уже за пределами таблицы.
