Максимальное время работы на одном тесте: 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 цифрами после точки.

   Решение

Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 60]      

В государстве царя Додона расположено 500 городов, каждый из которых имеет форму правильной 37-угольной звезды, в вершинах которой находятся башни. Додон решил обнести их выпуклой стеной так, чтобы каждый отрезок стены соединял две башни. Доказать, что стена будет состоять не менее чем из 37 отрезков. (Если несколько отрезков лежат на одной прямой, то они считаются за один.)

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

Решение

На плоскости даны четыре точки, не лежащие на одной прямой. Докажите, что существует неостроугольный треугольник с вершинами в этих точках.

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

Решение

На круглой сковороде площади 1 испекли выпуклый блин площади больше ½. Докажите, что центр сковороды находится под блином.

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

Решение

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

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

Решение

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

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

Решение

Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 60]