Версия для печати
Убрать все задачи

---

Максимальное время работы на одном тесте: 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  взаимно просты. Таблица заполняется следующим образом: пусть в некоторой строчке записаны числа  a₁, ..., a_k, a_k+1, ..., a_m, a_m+1, ..., a_n.  Тогда в следующей строчке записываются те же числа, но в таком порядке:  a_m+1, ..., a_n, a_k+1, ..., a_m, a₁, ..., a_k.  В первую строчку записываются (по порядку) числа  1, 2, ..., n.  Доказать, что после заполнения таблицы в каждом столбце будут написаны все числа от 1 до n.

   Решение

---

Имя входного файла:	necklace.in
Имя выходного файла:	necklace.out
Максимальное время работы на одном тесте:	1 секунда
Максимальный объем используемой памяти:	64 мегабайта
Максимальная оценка за задачу:	100 баллов

В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу.

Продавец хочет упорядочить колечки так, чтобы они располагались по возрастанию номеров вдоль нити по часовой стрелке. Снимать ожерелье с манекена нельзя.

Требуется написать программу, которая по заданному начальному расположению колечек находит последовательность протаскиваний колечек одно через другое, приводящую исходное расположение колечек в желаемое.

Формат входных данных

В первой строке входного файла записано число N (2 ≤ N ≤ 50).

Во второй строке через пробел следуют N различных чисел от 1 до N - номера колечек, расположенных вдоль нити по часовой стрелке.

Формат выходных данных

Выходной файл должен содержать описание процесса упорядочения.

В каждой строке, кроме последней, должны быть записаны через пробел два числа, указывающие номера колечек, протаскиваемых друг через друга. В последней строке должен стоять ноль.

Количество строк выходного файла не должно превышать 50000.

Если требуемого упорядочения колечек достичь не удается, в выходной файл нужно вывести одно число √1.

Пример

necklace.in	necklace.out
4 3 2 4 1	1 3 2 4 1 4 0

   Решение

---

В клетчатом квадрате 10×10 отмечены центры всех единичных квадратиков (всего 100 точек). Какое наименьшее число прямых, не параллельных сторонам квадрата,

нужно провести, чтобы вычеркнуть все отмеченные точки?

   Решение

Страница: 1 2 >> [Всего задач: 6]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 98296

Темы:   [ Геометрические интерпретации в алгебре ] [ Теорема косинусов ] [ Против большей стороны лежит больший угол ] [ Квадратичные неравенства (несколько переменных) ]

Сложность: 3+ Классы: 8,9,10

Положительные числа a, b, c таковы, что  a² + b² – ab = c².  Докажите, что (a – c)(b – c) ≤ 0.

Прислать комментарий

Решение

---

Задача 107810

Темы:   [ Геометрия на клетчатой бумаге ] [ Принцип Дирихле (конечное число точек, прямых и т. д.) ]

Сложность: 3+ Классы: 8,9,10

В клетчатом квадрате 10×10 отмечены центры всех единичных квадратиков (всего 100 точек). Какое наименьшее число прямых, не параллельных сторонам квадрата,

нужно провести, чтобы вычеркнуть все отмеченные точки?

Прислать комментарий

Решение

---

Задача 108681

Темы:   [ Правильный (равносторонний) треугольник ] [ Симметрия помогает решить задачу ] [ Сумма углов треугольника. Теорема о внешнем угле. ] [ Разбиения на пары и группы; биекции ]

Сложность: 4- Классы: 8,9

Точки P₁, P₂, ..., P_n–1 делят сторону BC равностороннего треугольника ABC на n равных частей:  BP₁ = P₁P₂ = ... = P_n–lC.  Точка M выбрана на стороне AC так, что  AM = BP₁.

Докажите, что  ∠AP₁M + ∠AP₂M + ... + ∠AP_n–1M = 30°,  если
  а)  n = 3;
  б) n – произвольное натуральное число.

Прислать комментарий

Решение

---

Задача 107812

Темы:   [ Шахматные доски и шахматные фигуры ] [ Теория игр (прочее) ] [ Доказательство от противного ] [ Принцип крайнего (прочее) ]

Сложность: 4 Классы: 8,9,10

В углу шахматной доски размером m×n полей стоит ладья. Двое по очереди передвигают её по вертикали или по горизонтали на любое число полей; при этом не разрешается, чтобы ладья стала на поле или прошла через поле, на котором она уже побывала (или через которое уже проходила). Проигрывает тот, кому некуда ходить. Кто из играющих может обеспечить себе победу: начинающий или его партнер, и как ему следует играть?

Прислать комментарий

Решение

---

Задача 107813

Темы:   [ Примеры и контрпримеры. Конструкции ] [ Системы точек ] [ Задачи на проценты и отношения ]

Сложность: 4 Классы: 7,8,9,10

  В стране, дома жителей которой представляют собой точки плоскости, действуют два закона:
    1. Человек может играть в баскетбол, лишь если он выше ростом большинства своих соседей.
    2. Человек имеет право на бесплатный проезд в транспорте, лишь если он ниже ростом большинства своих соседей.
  В каждом законе соседями человека считаются все люди, живущие в круге некоторого радиуса с центром в доме этого человека. При этом каждый человек сам выбирает себе радиус для первого закона и радиус (не обязательно такой же) для второго закона. Может ли в этой стране не менее 90% людей играть в баскетбол и не менее 90% людей иметь право на бесплатный проезд в транспорте?

Прислать комментарий

Решение

---

Страница: 1 2 >> [Всего задач: 6]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями