Страницы

Уроки 61,62 Задачи с геометрическим смылом

Задание 1.Даны размеры прямоугольных открытки и конверта. Требуется определить, поместиться ли открытка в конверт.

Ввод:
1 строка – два целых положительных числа - размер конверта.
2 строка – два целых положительных числа - размер открытки.
Вывод: да или нет.
Пример:


Input.txt
Output.txt
9  9
1 10
да


Примечание:
Открытка может быть размещена т.о., что ее стороны будут параллельны сторонам конверта. Также открытку можно разместить в конверте под наклоном:



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

Ввод:
Площадь четырехугольника (1<=n<=50000).
Вывод:
Стороны четырехугольников A и B.

Пример:
Input.txt
Output.txt
12
1 12
2  6
3  4



Задание 3. Отрезок на плоскости задается двумя несовпадающие конечными точками A (x1; y1) и B (x2; y2). Из точки С (х3; у3) к прямой, содержащей отрезок АВ, проводится перпендикуляр h. Определить, попадает перпендикуляр на отрезок АВ или на его продолжение.


Ввод:
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,
Если хотя бы одно неравенство нарушается, то перпендикуляр попадает на продолжение отрезка .

Задание 4. Кубик с ребром N см покрасили и разрезали на кубики с ребром 1 см. При этом появились такие, у которых окрашено разное количество граней. Например, если N = 3, то после разрезания будет 8 кубиков, у которых окрашено три грани, 12 с двумя гранями, 6 с одной, а один кубик будет совсем неокрашенный. Составьте программу, которая бы определяла, сколько кубиков с каждой возможным количеством окрашенных граней.

Ввод:  целое число N (от 1 до 1292)
Вывод: 
1 строка - количество кубиков с неокрашенными гранями
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.

Задание для самостоятельного решения

 На прямой задано 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].

Комментариев нет:

Отправить комментарий