Задача 3.
1. Выпуклый многоугольник задается координатами вершин при его обходе по часовой или против часовой стрелки. Контур многоугольника не имеет самопересечений. Определить направление обхода.
2. Выполнить то же самое, но только в случае невыпуклого многоугольника.
Задача 4.
Отрезок на плоскости задается двумя не совпадающими концевыми точками X(x1,x2) и Y(y1,y2). Из точки Z(z1,z2) к прямой, содержащей отрезок [X,Y], проводится перпендикуляр P.
Определить, попадает ли перпендикуляр P на отрезок [X,Y] или на его продолжение.
Задача 5.
Многоугольник на плоскости задается координатами своих N вершин в порядке обхода их по контуру по часовой стрелке. Считается, что контур самопересечений не имеет.
Найти площадь, периметр и углы многоугольника.
Задача 8.
1. Треугольник на плоскости задается целочисленными координатами вершин. Для заданной точки Z(x,y) определить, принадлежит ли она стороне треугольника или лежит внутри или вне его.
2. Многоугольник на плоскости задается координатами своих N вершин в порядке обхода их по контуру по часовой стрелке (контур самопересечений не имеет). Для заданной точки Z(x,y) определить, принадлежит ли она стороне многоугольника или лежит внутри или вне его.
Задача 9.
На плоскости заданы n отрезков координатами концевых точек. Концы отрезков задаются двумя парами координат (x1[i],y1[i]), (x2[i],y2[i]), 1<=i<=n (концы принадлежат отрезку).
Необходимо найти прямую, имеющую общие точки с максимальным числом отрезков, и напечатать в порядке возрастания номера тех отрезков, которые эта прямая пересекает.
Задача 10.
N точек на плоскости заданы своими координатами. Найти такой минимальный по площади выпуклый многоугольник, что все N точек лежат либо внутри этого многоугольника, либо на его границе (такой выпуклый многоугольник называется выпуклой оболочкой).
Задача 11.
На решетке размера m*n заданы k точек своими координатами. Необходимо определить, можно ли построить выпуклый многоугольник такой, что каждая точка принадлежит некоторой стороне.
Задача 12.
N точек на плоскости заданы своими координатами. Найти порядок, в котором можно соединить эти точки, чтобы получился N-угольник (т.е. не было бы пересечений сторон).
Задача 13.
Представьте себе, что в тетрадке Вы зарисовали на листе какое-то количество клеточек и получили клеточную фигуру.
Сколько осей симметрии имеет заданная клеточная фигура.
Пояснение :
1) Задается S - число тестов. Для каждого теста задаются NI размер фигуры по вертикали, NJ - размер фигуры по горизонтали (NI<101, NJ<81) и сама фигура в виде NI строк из пробелов и единиц по NJ символов в каждой строке.
2) Числа S, NI, NJ занимают при вводе по три позиции.
Пример .
Входные данные :
2 ( количество тестов )
2 ( размер 1-ой фигуры по вертикали )
4 ( размер 1-ой фигуры по горизонтали )
1111
1 1
3 ( размер 2-ой фигуры по вертикали )
5 ( размер 2-ой фигуры по горизонтали )
11111
111
111
Выходные сообщения:
1-АЯ ФИГУРА ИМЕЕТ 1 ОСЕЙ СИММЕТРИИ
2-АЯ ФИГУРА ИМЕЕТ 0 ОСЕЙ СИММЕТРИИ
Задача 14.
Прямоугольник ABCD задан координатами своих вершин. На противоположных сторонах AB и CD заданы последовательности R1 и R2 из N точек разбиения, а на сторонах BC и AD - R3 и R4 из M точек разбиения. Нумерация элементов последовательности R1 и R2 начинается соответственно от точек A и D, а в R3 и R4 -- от B и A. Соединив отрезками точки с одинаковыми номерами в разбиениях R1 и R2, а затем в разбиениях R3 и R4, получим разбиение Q прямоугольника ABCD на множество четырехугольников. Построить алгоритм, определяющий четырехугольник разбиения Q с наибольшей площадью, при условии, что отрезки, соединяющие точки разбиений R1 и R2 параллельны стороне AD. Последовательности R1, R2, R3 и R4 задаются как массивы из длин отрезков разбиения соответствующих сторон прямоугольника.
Задача 15.
На прямой задано N точек с координатами X1,X2,...,Xn. Написать программу, которая находит на прямой такую точку z, сумма расстояний от которой до данных N точек минимальна.
Задача 16.
На двумерной плоскости задано N точек с координатами (X1,Y1), (X2,Y2), ..., (Xn,Yn). Написать программу, которая находит такую точку Z(x,y), сумма расстояний от которой до остальных минимальна и:
а) Z - одна из заданных точек;
b) Z - произвольная точка плоскости.
Задача 17.
На плоскости расположены N точек, заданные своими координатами. Найти на оси абсцисс точку, наибольшее из расстояний от которой до выбранных точек было бы минимальным.
Задача 18.
На двумерной плоскости задано N точек с координатами (X1,Y1), (X2,Y2), ..., (Xn,Yn). Написать программу, которая из этих точек выделяет вершины квадрата, содержащего максимальное число заданных точек.
ПРИМЕЧАНИЕ: предполагается, что точки, расположенные на сторонах квадрата, принадлежат ему.
Задача 19.
Задано на плоскости множество из N прямоугольников, стороны которых параллельны осям координат, при этом каждый прямоугольник задается координатами левой нижней и правой верхней его вершин.
Составить алгоритм определения наибольшего натурального числа К, для которого существует точка плоскости, принадлежащая одновременно К прямоугольникам.
Примечание: эффективным считается алгоритм, число действий которого пропорционально Н2.
Задача 20.
На квадратном торте N свечей. Можно ли одним прямолинейным разрезом разделить его на две равные по площади части, одна из которых не содержала бы ни одной свечи? Свечи будем считать точками, у которых известны их целочисленные координаты Х[1], Y[1]; ...; Х[N], Y[N] (начало координат - в центре торта); разрез не может проходить через свечу.
Задача 21.
Даны N, N>1, прямоугольников, для которых предполагается, что:
А). Стороны любого прямоугольника параллельны координатным осям и прямоугольник задается концами одной из диагоналей.
В). Каждый прямоугольник имеет общие внутренние точки с хотя бы одним из остальных и не имеет общих вершин, сторон или частей сторон ни с одним из остальных прямоугольников.
Составить программу, которая решает следующие задачи:
1. С помощью последовательности точек определить внешний контур фигуры F, являющейся объединением прямоугольников - ломаную замкнутую кривую. Пример на чертеже.
2. Определить содержит ли фигура F "дырки" ,т.е. замкнутые фигуры, которые ей не принадлежат.
3. Разложить фигуру на наименьшее возможное число не пересекающихся прямоугольников, которые могут иметь общие стороны или части сторон , а их объединение дает фигуру F.
4. Вычислить периметр и площадь фигуры F.
Примечание.
1. Задачи 3,4 решаются только для фигур, которые не содержат "дырки".
2. Полное решение содержит:
-анализ (обоснование) решения
-текст программы с соответствующими комментариями
-выполнение текстового примера, который будет дан при приемке работы
Объединение прямоугольников Ai Bi Ci Di,i=1,2,3,4 есть
фигура F=A2 B2 X1 B1 X2 B4 C4 D4 X3 X4 C2 D2
фигура F содержит единственную "дырку" PQRS
Задача 22.
Очертание города.
Необходимо написать программу - помощник архитектора в рисовании очертания города. Город задается расположением зданий. Город рассматривается как двумерный и все здания в нем - прямоугольники, имеющие одинаковое основание (город построен на равнине). Здания задаются тройкой чисел (L[i],H[i],R[i]) где L[i] и R[i] есть координаты левой и правой стен здания i, а H[i] - высота этого здания. На рисунке 1 здания описываются тройками
(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29),(24,4,28)
а контур, показанный на рис. 2, задается последовательностью
(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0)
(о способе формировании этой последовательности см. ниже).
Рис. 1
Рис. 2
Ввод.
Ввод представляет собой последовательность троек, задающих дома. Все координаты есть целые числа, меньшие 10000. Во входном файле минимум одно и максимум 50 зданий. Каждая тройка, обозначающая здание находится в отдельной строке во входном файле. Все целые числа в тройке разделены одним или несколькими пробелами. Тройки отсортированы по L[i], т.е. по левой х-координате здания, таким образом, здание с самой маленькой левой х-координатой является первым во входном файле.
Вывод.
Вывод будет состоять из вектора, описывающего очертание, как показано в примере выше. В векторе очертания (v[1],v[2],v[3], ... , v[n-2],v[n-1],v[n]), v[i], когда i-четное число, означает горизонтальную линию (высоту). Когда i-нечетное, v[i]-означает вертикальную линию (х-координату). Вектор очертания будет определять маршрут, пройденный, к примеру, жуком, начавшим с минимальной х-координаты и путешествующим по всем вертикальным и горизонтальным линиям, определяющим контур. Последний элемент в векторе линии контура будет 0.
Задача 23.
Нижняя левая и верхняя правая вершины прямоугольника A имеют координаты (0,0) и (V,W) соответственно. Множество S из N точек задается парами координат (x[i],y[i]), 1<=i<=N.
Найти такой прямоугольник G максимальной площади, что его стороны параллельны сторонам A, G полностью лежит в A (G и A могут иметь общие граничные точки) и ни одна точка из S не лежит внутри G (но может лежать на его стороне). Напечатать величину площади G и координаты нижней левой и верхней правой вершин этого прямоугольника.
Если таких прямоугольников несколько, то вывести информацию по каждому.
Замечание: в множестве S никакие две точки не лежат на одной прямой, параллельной стороне A.
Необходимо:
1. Организовать ввод данных в виде
< Введите V и W -- координату верхней правой вершины прямоугольника A >
< Введите N -- число точек >
< Введите координаты точек >
x[1]--> y[1]-->
.....
x[N]--> y[N]-->
2. Вывести результаты в виде
< Максимальная площадь прямоугольника = >
< Координаты нижней левой и верхней правой вершин прямоугольника(ов) >
x1--> y1--> x2--> y2-->
Задача 24.
В первом квадранте координатной системы OXY нарисован первый квадрат - ABCD, длина стороны которого равна 1 и вершина A находится в начале координат. Потом нарисованы: второй квадрат - BEFC, третий - DFGH, четвертый - JAHI, пятый- KLEJ, шестой - LMNG, и так далее 'по спирали' (рис.1).
Написать программу, которая для введенных целых чисел x и y определяет и выводит номер квадрата, которому принадлежит точка P(x;y). Если точка P лежит на сторонах квадратов или в вершинах, то будем считать, что она принадлежит квадрату с наименьшим номером из возможных.
Примеры:
X
Y
Результат
2
1
1
-1
0
4
13
2
10
Рис.1
Задача 25.
На плоскости N различных точек заданы своими координатами. Найти уравнение прямой, делящей это множество точек на 2 равномощных подмножества (т.е. на подмножества с одинаковым количеством элементов).
Задача 27.
N-угольник на плоскости задается координатами вершин в порядке обхода по контуру (контур самопересечений не имеет). Для точки Z(x,y) найти минимальное расстояние до контура N-угольника.
Задача 28.
На плоскости задано N точек своими координатами и матрица C(N*N); C(i,j)=C(j,i)=1 в случае, если вершины i и j соединены отрезком и 0 иначе. Известно, что любая вершина соединена по крайней мере с двумя другими, и что отрезки пересекаются только в концевых точках. Таким образом, вся плоскость разбивается на множество многоугольников. Задана точка Z(x,y). Найти минимальный по площади многоугольник, содержащий Z, или выдать сообщение, что такого не существует. Если Z принадлежит какому-то отрезку, то выдать его концевые точки, если Z лежит в многоугольнике, то выдать его вершины в порядке обхода по контуру.
Задача 29.
Будем называть два многоугольника подобными, если существует взаимно-однозначное отображение сторон этих двух фигур такое, что соответствующие стороны пропорциональны с коэффициентом пропорциональности k, а углы, образованные двумя соответствующими сторонами, равны.
Определить, подобны ли два многоугольника. Многоугольники задаются на плоскости координатами вершин контуров. Вершины в контуре перечисляются в порядке обхода против часовой стрелки.
Примечание: так как все вычисления на ЭВМ проводятся с ограниченной точностью, то считать, что две величины равны если они совпадают с точностью до двух знаков после запятой.
ВВОД: <из файла T.TXT>
<Количество вершин в контуре:> N
<Многоугольник 1:>
<Координаты вершины 1:> x11, y11
.....
<Координаты вершины N:> x1N, y1N
<Многоугольник 2:>
<Координаты вершины 1:> x21, y21
.....
<Координаты вершины N:> x2N, y2N
ВЫВОД:
<Многоугольники не подобны>
или
<Многоугольники подобны с k=> k
Задача 30.
Заданы натуральное N и две последовательности целых чисел (а1,а2,...,аn) и (b1,b2,...,bn). Заданы также два числа X0 и X1, X0<X1.
1. Найти числа t(0), t(1), ..., t(p), p<=N, такие ,что X0=t(0)<t(1)<...<t(p)=X1 и указать для каждого отрезка [t(j-1), t(j)], 1<=j<=p, такое число k, 1<=k<=N, что для всех i, 1<=i<=N, и для всех x из [t(j)-1,t(j)] справедливо неравенство аk*x+bk>=аi*x+bi.
2.Найти числа s(0), s(1), ..., s(Q), таки, что X0=s(0)< <s(1)<...<s(Q)=X1, и указать для каждого отрезка [s(j-1),s(j)], 1<=j<=Q, такую перестановку (i1,i2,...,iN) чисел 1,2,3,...,N, что для всех x из [s(j-1),s(j)] справедливо неравенство
ai1*x+bi1<=аi2*x+bi2<=...<=аiN*x+biN
и для всех отрезков соответствующие перестановки различны.
Задача 31.
На плоскости задано множество точек А и множество прямых В. Найти две такие различные точки из А, что проходящая через них прямая параллельна наибольшему количеству прямых из В.
Задача 32.
В правильном n-угольнике провели несколько диагоналей, причем никакие три не пересекаются в одной точке. На сколько частей диагонали разбили n-угольник? Диагонали заданы номерами вершин n-угольника,которые они соединяют, все вершины перенумерованы по порядку числами 1, ...,n.
Задача 33.
Круг разрезан несамопересекающейся ломаной, координаты вершин которой заданы парами натуральных чисел (x1,y1), ..., (xk,yk). Первая и последняя вершины лежат на границе круга, а остальные внутри его. Определить, можно ли разъединить две получившиеся части круга (выход из плоскости и повороты разнимаемых частей не допускается).
Задача 34.
Среди треугольников с вершинами в заданном множестве точек на плоскости указать такой, стороны которого содержат максимальное число точек заданного множества.
Задача 35.
Все стены дома имеют длину 5м. Северная и южная стороны-белые, западная и восточная-синие. Человек прошел от юго-восточного угла дома А метров на юг, В метров на восток и С метров север и посмотрел на дом.
Написать алгоритм, который определяет, что видит человек.
Задача 36.
На местности, представляющей собой идеально ровную поверхность, стоит высокий забор. План забора представляет собой замкнутую ломаную без самопересечений. Эта ломаная задается N парами координат своих вершин в порядке обхода ограничиваемой забором области против часовой стрелки. Вершины пронумерованы от 1 до N, N<100.
В точке (x,y) стоит человек ((x,y) не может лежать на ломаной). Считая, что каждому звену ломаной становится в соответствие пара номеров концевых вершин, указать, какие звенья человек увидит полностью или частично в качестве невырожденного отрезка, а какие - вообще нет. Если при взгляде звено видно как точка или как пара, точек, то полагаем, что оно не видно.
Задача 37.
На гранях двух равных правильных тетраэдров N и M написаны числа N1,N2,N3,N4 и M1,M2,M3,M4.
Можно ли совместить тетраэдры так, чтобы на совпадающих гранях оказались одинаковые числа?
Задача 38.
На столе лежит игральный кубик гранью A0 к нам, гранью B0 вверх. Написать программу определяющую последовательность "кантования" кубика ("на нас", "от нас", "вправо", "влево"), после выполнения которых кубик окажется на прежнем месте, но к нам гранью Ak, вверх - Bk.
ПРИМЕЧАНИЕ: Под кантованием понимается перекатывание кубика через соприкасающееся со столом ребро без скольжения. Другие способы перемещения кубика запрещены. Нумерация граней кубика такова, что если его положить на грань с цифрой"5", то боковые грани будут иметь номера"1","6","4","3" при обходе по часовой стрелке, а верхняя - номер "2".
