Next:6.5 Игры
Up:6 Формулировки заданий
Previous:6.3 Формулы и программы
 

6.4 Геометрия

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

2.  Определить радиус и центр окружности, на которой лежит наибольшее число точек заданного на плоскости множества точек.

3.  Задано множество  точек на плоскости. Определить, верно ли, что для каждой точки существует точка такая, что не существует двух точек множества , лежащих по разные стороны от прямой .

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

5.  В заданном множестве точек на плоскости найти пару точек с максимальным расстоянием между ними.

6. Расстояние между двумя множествами точек -- это расстояние между наиболее близко расположенными точками этих множеств. Найти расстояние между двумя заданными множествами точек на плоскости.

7.  Многоугольник (не обязательно выпуклый) задан на плоскости перечислением координат вершин в порядке обхода многоугольника по границе. Определить площадь многоугольника.

8.  Задано множество точек  в трехмерном пространстве. Найти такую из них, что шар заданного радиуса с центром в этой точке содержит максимальное число точек из .

9.  Задано множество прямых на плоскости (коэффициентами своих уравнений). Подсчитать количество точек пересечения этих прямых.

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

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

12. Порядок на точках плоскости определим следующим образом: (x,y)  < (u,v), если либо x < u , либо x=u и y<v.
Перечислить точки заданного множества точек на плоскости в соответствии с так определенным порядком.

13.  Заданы два множества точек на плоскости. Построить пересечение и разность этих множеств.

14.  Множество точек на плоскости назовем регулярным, если вместе с каждой парой различных точек оно содержит также еще одну -- третью -- вершину правильного треугольника с вершинами в этих точках. Определить, регулярно ли заданное множество точек.

15.  На плоскости задано  множеств по  точек в каждом. Среди точек первого множества найти такую, которая принадлежит наибольшему количеству множеств.

16.  На плоскости заданы два множества: точек  и окружностей . Найти две такие различные точки из , что проходящая через них прямая пересекается с максимальным количеством окружностей из .

17.  На плоскости заданы два множества: точек  и прямых линий . Найти две такие различные точки из , что проходящая через них прямая линия параллельна наибольшему количеству прямых из .

18.  На плоскости заданы множество точек и точка вне его. Подсчитать количество (неупорядоченных) различных троек точек из  таких, что четырехугольник является параллелограммом.

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

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

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

22.  Задано множество точек в трехмерном пространстве. Найти минимум радиуса шара с центром в одной из этих точках, который содержит ровно  точек этого множества.
 

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

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

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

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

27.  Из заданного множества точек на плоскости выбрать три разные точки  так, чтобы внутри треугольника содержалось максимальное количество точек этого множества.

28.  Из заданного множества точек на плоскости выбрать две различные точки так, чтобы окружности заданного радиуса с центрами в этих точках содержали внутри себя одинаковое количество точек множества.

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

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

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

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

33.  На плоскости задано множество попарно различных прямых (коэффициентами своих уравнений). Указать среди них ту прямую, которая имеет максимальное число пересечений с остальными прямыми.

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

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

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

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

38.  Найти ромб наибольшей площади с вершинами в заданном множестве точек на плоскости.

39.  Подсчитать количество равносторонних треугольников с различными длинами оснований и вершинами в заданном множестве точек на плоскости.

40.  Задано множество точек на плоскости, не лежащих на одной прямой. Определить минимальное подмножество точек, после удаления которых остаются точки, лежащие на одной прямой.

41.  Построить множество всех различных выпуклых четырехугольников с вершинами в заданном множестве точек на плоскости.

42.  Построить множество всех различных остроугольных треугольников с вершинами в заданном множестве точек на плоскости.

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

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

45. Среди треугольников с вершинами в заданном множестве точек на плоскости указать такой, стороны которого содержат максимальное число точек заданного множества.

46.  Построить два треугольника с вершинами в заданном множестве точек на плоскости так, чтобы первый треугольник лежал строго внутри второго.

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

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

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

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

51. Трасса для соревнований задана в виде -угольника , в одной из вершин которого находится место старта, а одна из сторон -- линия финиша (место старта -- не на линии финиша!). Путь по трассе представляет собой ломаную внутри -угольника от старта к финишу. Каждый отрезок ломаной проходится за единицу времени и является вектором скорости (в этот момент) с целочисленными координатами. В соседние моменты времени компоненты векторов скорости должны либо совпадать, либо отличаться на единицу. Длина вектора начальной скорости равна нулю. Найти минимальное время прохождения трассы.

52. В условиях предыдущего задания найти минимальный по длине путь по трассе.

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

54. Построить такой многоугольник (не обязательно выпуклый) с вершинами в заданном на плоскости множестве точек, периметр которого максимален.

55. Найти минимальное множество прямых, на которых можно разместить все точки заданного на плоскости множества точек.

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

57. Найти минимальное множество окружностей, на которых можно разместить все точки заданного на плоскости множества точек.

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

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

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

61.  Построить синтаксический анализатор для определяемого в словаре понятия список-геометрических-фигур.

62.  Проверить, является ли корректным заданный список геометрических фигур.

63.  Подсчитать сумму площадей заданного корректного списка геометрических фигур.

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

65.  Для заданного корректного списка геометрических фигур определить, верно ли, что ограничивающие эти фигуры линии попарно не пересекаются.
 

66.  Для заданного корректного списка геометрических фигур определить, верно ли, что всякая окружность списка описана вокруг некоторого треугольника или квадрата из этого списка.

67.  Из заданного списка фигур удалить все некорректные фигуры, а также повторные описания корректных фигур.

68.  Найти точку пересечения границ всех фигур, перечисленных в заданном корректном списке фигур.

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

70.  Для заданного корректного списка геометрических фигур определить, есть ли среди них такая фигура, что все остальные фигуры списка расположены внутри нее.

71.  Для заданного корректного списка геометрических фигур определить, верно ли, что каждая окружность из этого списка построена на одной из сторон треугольника или квадрата как на диаметре.

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

73. Задано множество точек на плоскости. Найти максимальный по площади невырожденный многоугольник без пересечений и самокасаний, вершины которого образуют подмножество заданного множества точек.

74.  На плоскости задано множество окружностей. Определить площадь их пересечения.

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

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

77. В трехмерном пространстве задано  шаров. Найти шар минимального радиуса, охватывающий все заданные.

78. Лежащий на плоскости круг разрезан непересекающейся ломаной, вершины которой имеют целочисленные координаты. Определить, можно ли разъединить две получившиеся части круга, перемещая их по плоскости.

79. Задано множество точек в трехмерном пространстве. Напечатать (без повторения) все такие тройки точек , что все остальные точки лежат по одну сторону от плоскости, проходящей через .

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

81. Найти кратчайшую ломаную линию, проходящую через  заданных точек на плоскости.

82. На плоскости заданы точек. Объединить их в пары, соединив отрезками так, чтобы сумма длин отрезков была минимальной.

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

84. Найти шар минимального радиуса, охватывающий все заданные точки в трехмерном пространстве, с центром в одной из этих точек.

85. Задано  точек на плоскости. Найти окружность наибольшего радиуса, не содержащую внутри ни одной точки этого множества, центр которой лежит внутри выпуклой оболочки заданного множества точек.

86. Задано  точек на плоскости. Построить дерево с вершинами в данных точках так, чтобы была минимальной суммарная длина его ребер.

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

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

90. Проверить, пересекаются ли два заданных многоугольника на плоскости.

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

92. На плоскости задано  прямоугольников. Найти площадь той части плоскости, которую они накрывают.

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

94. Задано  прямоугольников на плоскости. Найти контур их объединения -- минимальный многоугольник, охватывающий все заданные прямоугольники.

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

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

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

98. Задано  точек на плоскости. Известно, что эти точки -- это объединение вершин некоторого "большого" треугольника и вершин треугольников, образующих разбиение большого треугольника на множество меньших треугольников. Построить все треугольники.

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

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

Next:6.5 Игры
Up:6 Формулировки заданий
Previous:6.3 Формулы и программы