Задание 1.Даны размеры прямоугольных открытки и конверта. Требуется определить, поместиться ли открытка в конверт.
Примечание:
Открытка может быть размещена т.о., что ее стороны будут параллельны сторонам конверта. Также открытку можно разместить в конверте под наклоном:
Задание 3. Отрезок на плоскости задается двумя несовпадающие конечными точками A (x1; y1) и B (x2; y2). Из точки С (х3; у3) к прямой, содержащей отрезок АВ, проводится перпендикуляр h. Определить, попадает перпендикуляр на отрезок АВ или на его продолжение.
Ввод:
1 строка - два вещественных числа - координата точки А.
2 строка - два вещественных числа - координата точки В.
3 строка - два вещественных числа - координата точки С.
Вывод: «На отрезок» или «На продолжение»
Пример:
Задание 4. Кубик с ребром N см покрасили и разрезали на кубики с ребром 1 см. При этом появились такие, у которых окрашено разное количество граней. Например, если N = 3, то после разрезания будет 8 кубиков, у которых окрашено три грани, 12 с двумя гранями, 6 с одной, а один кубик будет совсем неокрашенный. Составьте программу, которая бы определяла, сколько кубиков с каждой возможным количеством окрашенных граней.
Ввод:
1 строка – два целых положительных числа - размер конверта.
2 строка –
Вывод: да или нет.
Пример:
Input.txt
|
Output.txt
|
9 9
1 10
|
да
|
Примечание:
Открытка может быть размещена т.о., что ее стороны будут параллельны сторонам конверта. Также открытку можно разместить в конверте под наклоном:
Задание 2. Прямоугольники, площади которых равны, называются равновеликими. Написать программу, находящую все возможные целочисленные стороны равновеликих прямоугольников заданной площади.
Ввод:
Площадь четырехугольника (1<=n<=50000).
Площадь четырехугольника (1<=n<=50000).
Вывод:
Стороны четырехугольников A и B.
Пример:
Input.txt
|
Output.txt
|
12
|
1 12
2 6 3 4 |
Ввод:
1 строка - два вещественных числа - координата точки А.
2 строка - два вещественных числа - координата точки В.
3 строка - два вещественных числа - координата точки С.
Вывод: «На отрезок» или «На продолжение»
Input.txt
|
Output.txt
|
3 3
6 2 8 4 |
На продолжении
|
Примечание.
Пусть a, b и c - длины отрезков AB, BC и AC соответственно. Если перпендикуляр h попадает на отрезок AB, то углы ABC и BAC по величине не превосходят 90 градусов (эти оба угла острые).
По теореме косинусов
По теореме косинусов
b2 = a2 + c2 - 2*a*a*cos BAC и c2 = a2 + b2 - 2*a*b*cos ABC
Если углы ABC и BAC не тупые, то cos BAC и cos ABC лежат в пределах от 0 до 1, и слaгаемые -2*B*C*cos BAC и -2*A*B*cos ABC в приведенных выше формулах неположительны, т.е. в случае, когда перпендикуляр попадает на отрезок AB, должны выполняться одновременно два неравенства
b2 >= a2 + c2 и c2 >= a2 + b2,
Если хотя бы одно неравенство нарушается, то перпендикуляр попадает на продолжение отрезка .
Ввод: целое число N (от 1 до 1292)
Вывод:
Вывод:
1 строка - количество кубиков с неокрашенными гранями
2 строка - количество кубиков с одной окрашенной гранью
3 строка - количество кубиков с двумя окрашенными гранями.
4 строка - количество кубиков с тремя окрашенными гранями.
2 строка - количество кубиков с одной окрашенной гранью
3 строка - количество кубиков с двумя окрашенными гранями.
4 строка - количество кубиков с тремя окрашенными гранями.
Пример:
Input.txt
|
Output.txt
|
3
|
1
6
12
8
|
Задание 5. Три круга (колеса), диаметры которых равны d1, d2, d3, расположены таким образом, что их центры находятся на одной прямой и первый круг соприкасается со вторым, а второй - с третьим. Вращение одного из кругов (колес) приводит во вращение остальные. Через какое минимальное число оборотов каждого из кругов они придут в начальное положение?
Ввод: d1, d2, d3 - натуральные числа
Вывод:
1 строка - число оборотов первого круга
2 строка - число оборотов второго круга.
3 строка - число оборотов третьего круга.
Пример:
Input.txt
|
Output.txt
|
9 4 12
|
4
9 3 |
Примечание: Обозначим k1, k2, k3 число оборотов каждого из кругов. Расстояние, которое проходят точки, лежащие на внешних окружностях каждого из кругов, должно быть одинаково, т.е. k1*pi*d1=k2*pi*d2=k3*pi*d3.
Сократим на pi и обозначим s=k1*pd1=k2*d2=k3*d3.
Т.к. k1, k2, k3 должны быть минимальными, то s=НОК(d1,d2,d3).
Тогда k1=НОК(d1,d2,d3) div d1;
k2=НОК(d1,d2,d3) div d2;
k3=НОК(d1,d2,d3) div d3.
Сократим на pi и обозначим s=k1*pd1=k2*d2=k3*d3.
Т.к. k1, k2, k3 должны быть минимальными, то s=НОК(d1,d2,d3).
Тогда k1=НОК(d1,d2,d3) div d1;
k2=НОК(d1,d2,d3) div d2;
k3=НОК(d1,d2,d3) div d3.
Задание для самостоятельного решения
На прямой задано N точек с координатами X1,X2,...,Xn. Написать программу, которая находит на прямой такую точку z, сумма расстояний от которой до данных N точек минимальна.
Указание: Пусть координаты точек x[1], ..., x[N] не убывают (если это не так, то просто отсортируем предварительно последовательность).
Пусть мы решаем задачу для N точек на прямой.
Точка z должна, очевидно, лежать на отрезке [x[1],x[N]].
Если N=1, то данная точка и является искомой.
Если N=2, то z может лежать где угодно на отрезке [x[1],x[N]] - суммарное расстояние будет одинаковым и равным длине отрезка. Если N>2, то суммарное расстояние от точки z до точек с минимальной и максимальной координатами (т.е. до точек x[1] и x[N]) не зависит от местоположения точки z и равно длине отрезка [x[1], x[N]]. Так как суммарное расстояние до этих двух точек постоянно, то поэтому мы можем их отбросить, и решать задачу уже для N-2 точек x[2],...,x[N-1]. Проведя необходимое число раз сокращение количества точек, мы придем к уже рассмотренным случаям одной или двух точек.
Окончательно получаем: если N=2k, то точка z может быть любой из точек отрезка [x[k],x[k+1]], если же N=2k+1, то точка z=x[k+1].
