Тема 1.1. Геометрия.
Цель.
Научиться применять знания по геометрии при решении задач с использованием компьютеров (программ). Уметь выполнять приближённые вычисления с точностью.
Основные понятия.
Вычисления с вещественными числами с заданной точностью. Использование математических функций: sin, cos, fabs, exp, log
Вывод вещественных чисел в нужном формате. Использование манипуляторов и форматов: setw, setiosflags, setprecision
Ключевые слова.
Точка, уравнение прямой линии, геометрическая фигура.
ПРИМЕР.
На плоскости три точки заданы своими целыми (для простоты) координатами. Они образуют невырожденный треугольник. Вычислить площадь этого треугольника.
Алгоритм.
Можно воспользоваться одной из формул, знакомых со школы. Для этого придётся вычислить какие-то элементы треугольника – стороны, углы, периметр. Мы воспользуемся формулой, дающей значение площади со знаком в зависимости от направления обхода вершин треугольника – через определитель 3-го порядка.
| 1 x1 y1 |
S = | 1 x2 y2 | * 0.5
| 1 x3 y3 |
Решение.
// C++
# include <iostream>
# include <iomanip>
# include <сstdlib>
using namespace std;
int main ()
{
setlocale (LC_ALL, "RUS");
cout << "Вычисление площади треугольника со знаком." << endl;
cout << "Введите координаты вершин." << endl;
int x1, y1, x2, y2, x3, y3;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
double s = 0.5*(x1*y2 + x2*y3 + x3*y1 – x1*y3 – x2*y1 - x3*y2);
cout << setiosflags (ios::fixed) << setw (10)
<< setprecision (2) << s << endl;
system ("PAUSE"); // другой вариант задержки результатов на экране
return 0;
}
// C#
using System;
class Program
{
static void Main (string [] args)
{
Console.Write ("Вычисление площади треугольника со знаком. ");
Console.Write ("Введите координаты вершин ");
int x1, y1, x2, y2, x3, y3;
string ss = Console.ReadLine ();
string [] s = ss.Split (' ');
x1 = int.Parse (s [0]);
y1 = int.Parse (s [1]);
x2 = int.Parse (s [2]);
y2 = int.Parse (s [3]);
x3 = int.Parse (s [4]);
y3 = int.Parse (s [5]);
double sq = 0.5*(x1*y2 + x2*y3 + x3*y1 - x1*y3 - x2*y1 - x3*y2);
Console.WriteLine (sq);
Console.ReadKey ();
}
}
Задачи для обязательного решения.
1.1.1.1. Составить уравнение прямой AХ +BY+C= 0, проходящей через 2 заданные точки (X1,Y1) и (X2,Y2). Напечатать полученные коэффициенты этой прямой.
Исходные данные:
0 0
1 1
Результат:
1.0 -1.0 0.0
1.1.1.2. Для двух прямых, заданных своими уравнениями A1Х +B1Y+C1=0 иA2Х +B2Y+C2=0 найти точку пересечения, если она есть. Если прямые не пересекаются, то напечатать слово «НЕТ», если прямые совпадают, то напечатать слово «МНОГО». Вводятся целые коэффициенты А, В, С каждого уравнения.
Исходные данные:
1 1 0
1 -1 0
Результат:
0 0
1.1.1.3. Дано уравнение прямой AХ +BY+C= 0 и координаты некоторой точки (Х,Y). Найти кратчайшее расстояние от точки до прямой и напечатать с точностью 3 знака после запятой. Вводятся целые коэффициенты А, В, С уравнения в одной строке и целые координаты точки в другой.
Исходные данные:
1 1 0
0 1
Результат:
1.000
1.1.1.4. Даны целые координаты трёх точек (Х1,Y1), (Х2,Y2), (Х3,Y3). Определить, лежат ли эти три точки на одной прямой и напечатать «ДА» или напечатать «НЕТ».
Исходные данные:
2 3
3 4
4 5
Результат:
ДА
1.1.1.5. Дано уравнение прямой AХ +BY+C= 0 (задаются коэффициенты А, В, С) и координаты двух точекT1(Х1,Y1) иT2(Х2,Y2). Все числа целые. Напечатать «ДА», если обе точки находятся по одну сторону от прямой, т.е. отрезокT1T2не пересекает прямую. В противном случае напечатать «НЕТ».
Исходные данные:
1 1 0
1 1
-1 -1
Результат:
НЕТ
1.1.1.6. Даны координаты четырёх точек (Х1,Y1), (Х2,Y2), (Х3,Y3), (Х4,Y4) в порядке обхода по часовой стрелке. Вычислить и напечатать площадь этого четырёхугольника
Исходные данные:
0 0
0 1
1 1
1 0
Результат:
1.0
1.1.1.7. Даны координаты четырёх точек (Х1,Y1), (Х2,Y2), (Х3,Y3), (Х4,Y4) в порядке обхода по часовой стрелке. Определить и напечатать тип (название) этого четырёхугольника – ромб, квадрат, параллелограмм, трапеция, прямоугольник, общего вида.
Исходные данные:
0 0
0 1
1 1
1 0
Результат:
КВАДРАТ
1.1.1.8. Два влюблённых крокодила (Х1,Y1) и (Х2,Y2) находятся на периметре квадратного бассейна заданного размера А (А > 0). Левый нижний угол бассейна имеет координаты (0,0). Найти кратчайшее расстояние между ними по периметру, т.е. запрещается пересекать бассейн.
Исходные данные:
0 0
0 1
10
Результат:
1
1.1.1.9. Даны целые координаты nточек на плоскости (Х1,Y1), ..., (Хn,Yn). Определить, лежат ли эти три точки на одной прямой, и напечатать «ДА» или напечатать «НЕТ». В первой строке задаётся натуральное числоn– количество точек, в следующихnстроках задаются пары целых чисел – координаты точек.
Исходные данные:
3
2 3
3 4
4 5
Результат:
ДА
Задачи для самостоятельного решения.
1.1.2.1. Вычислить и напечатать количество целочисленных точек, которые находятся внутри круга радиуса Rи с центром в точке (X,Y). Точки на границе учитывать.
Исходные данные:
2 0 0
Результат:
13
1.1.2.2. Вычислить и напечатать количество целочисленных точек, которые находятся внутри треугольника, заданного координатами вершин (Х1,Y1), (Х2,Y2), (Х3,Y3). Точки на границе учитывать.
Исходные данные:
0 0
2 0
0 2
Результат:
6
1.1.2.3. Вычислить и напечатать количество целочисленных точек, которые находятся внутри четырехугольника, заданного координатами вершин (Х1,Y1), (Х2,Y2), (Х3,Y3) , (Х4,Y4) в порядке обхода периметра по часовой стрелке. Точки на границе учитывать.
Исходные данные:
0 0
2 0
2 2
0 2
Результат:
9
1.1.2.4. Найти кратчайшее расстояние между 2 точками (Х1,Y1) и (Х2,Y2), не пересекающее заданный круг радиусаRи с центром в точке (X,Y). Касание допускается. В первой строке задаются координаты первой точки Х1,Y1, во второй – координаты второй точки Х2,Y2. В третьей строке задаётся координаты центра круга Х ,Yи радиус R. Напечатать ответ с точностью 4 знака после запятой.
Исходные данные:
0 0
0 4
1 1 1
Результат:
4.0000
1.1.2.5. Найти кратчайшее расстояние между 2 точками, не пересекающее заданный квадрат. В первой строке задаются координаты первой точки Х1,Y1, во второй – координаты второй точки Х2,Y2. В третьей строке задаётся левая нижняя вершина квадрата (ХХ ,YY) и длина стороны А (стороны параллельным осям координат). Напечатать ответ с точностью 4 знака после запятой.
Исходные данные:
0 0
3 4
1 1 2
Результат:
5.3983
1.1.2.6. Даны два круга радиуса R1 с центром в точке (Х1,Y1) и радиусаR2с центром в точке (Х2,Y2). Найти площадь общей части этих фигур.
Исходные данные:
2 0 0
3 10 10
Результат:
0
1.1.2.7. Две точки (Х1,Y1) и (Х2,Y2) начинают равномерное движение каждая со своей скоростью и каждая в своём направлении. Векторы скоростей задаются точками (X3,Y3) и (X4,Y4). Найти кратчайшее расстояние между ними и напечатать его с точностью 3 знака после запятой.
Исходные данные:
0 0
2 0
0 1
1 0
Результат:
2.000
1.1.2.8. Шар на бильярдном столе. На столе прямоугольного бильярда размером AнаBи со сторонами, параллельными осям координат в некоторой заданной точке (X,Y) находится точечный шар, который начинает двигаться в заданном направлении (под углом Аlpha). Определить координаты шара после прохождения расстоянияL. Все отражения от бортов неупругие и угол падения равен углу отражения.
Исходные данные:
Результат:
1.1.2.9. Шар на круглом бильярдном столе. На столе круглого бильярда радиуса rв некоторой заданной точке (X,Y) находится точечный шар, который начинает двигаться в заданном направлении (под углом Аlpha). Определить координаты шара после прохождения расстоянияL. Все отражения от бортов неупругие и под углом падения к касательной.
Исходные данные:
Результат:
1.1.2.10. Квадрат. Треугольник задан на плоскости координатами своих вершин: Х1,Y1, Х2,Y2, Х3,Y3. Найти длину L стороны квадрата минимальной площади и со сторонами, параллельными осям координат, в который можно поместить этот треугольник так, чтобы все вершины треугольника находились внутри квадрата либо на его сторонах. В первых трёх строках задаются координаты вершин треугольника. Напечатать ответ с точностью 4 знака после запятой.
Исходные данные:
0 0
0 4
1 1
Результат:
4.0000
1.1.2.11. Даны координаты вершин двух квадратов (Х1,Y1), (Х2,Y2), (Х3,Y3) , (Х4,Y4) и (ХX1,YY1), (XХ2,YY2), (XХ3,YY3) , (XХ4,YY4) в порядке обхода по часовой стрелке. Найти и напечатать площадь общей части этих фигур. В первой строке находятся 8 целых чисел –координаты вершин первого квадрата, во второй – второго квадрата. Гарантируется, что фигуры – квадраты. Результат напечатать с точностью 3 знака после запятой.
Исходные данные:
0 0 0 2 2 2 2 0
1 1 1 4 4 4 4 1
Результаты:
1.000
1.1.2.12. Даны координаты вершин двух прямоугольников (Х1,Y1), (Х2,Y2), (Х3,Y3) , (Х4,Y4) и (ХX1,YY1), (XХ2,YY2), (XХ3,YY3) , (XХ4,YY4) в порядке обхода по часовой стрелке. Найти и напечатать площадь общей части этих фигур. В первой строке находятся 8 целых чисел –координаты вершин первого квадрата, во второй – второго квадрата. Гарантируется, что фигуры – квадраты. Результат напечатать с точностью 3 знака после запятой.
Исходные данные:
0 0 0 2 5 2 5 0
1 1 1 4 4 4 4 1
Результаты:
3.000
1.1.2.13. Точки отрезка. Требуется написать программу, которая вычислит, сколько всего точек с целочисленными координатами принадлежат этому отрезку. Вводятся четыре целых числа – координаты концов отрезка (x1, y1) и (x2, y2). Каждая из координат не превышает по абсолютной величине значения 109. Вывести одно число – количество точек на заданном отрезке, имеющих целочисленные координаты.
Исходные данные:
1 1 2 2
Результаты:
2
1.1.2.14. Дремучий лес. Будем говорить, что для наблюдателя лес является дремучим, если из своего текущего положения наблюдатель видит только деревья. Вам дана карта леса и координаты точки, в которой находится наблюдатель. Требуется определить, кажется ли лес дремучим данному наблюдателю. На карте леса все деревья изображаются кругами. При этом в лесу бывают сросшиеся деревья (изображения таких деревьев на карте пересекаются), также одно дерево может находиться внутри другого. Точка, в которой стоит наблюдатель, не лежит внутри или на границе ни одного из деревьев. В первой строке содержится сначала целое число N — количество деревьев (1<=N<=50000). Во второй строке идут два числа, задающих координаты наблюдателя. Затем идет N строк с тройкой чисел, задающих деревья. Первые два числа задают координаты центра, а третье — радиус. Все координаты задаются точно, и выражаются вещественными числами не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 100000. Вывести сообщение YES, если лес является дремучим, и NO иначе.
Исходные данные:
4 0 0 2 2 2 -2 2 2 -2 -2 2 2 -2 2
Результаты:
YES
1.1.2.15. Открытка и конверт. Даны размеры прямоугольной открытки и прямоугольного конверта. Требуется определить, поместится ли открытка в конверте. В первой строке размеры открытки, во второй строке заданы размеры конверта. Все размеры – натуральные числа, не превосходящие 100. Вывести «Possible», если открытку можно разместить в конверте, и «Impossible» в противном случае.
Исходные данные:
1 10 9 9
Результаты:
Possible
1.1.2.16. Фонарики. Даны два одинаковых круга. В первых двух строчках содержатся координаты (x1,y1) и (x2,y2) - центры двух кругов. В третьей строке задан радиус r описанных выше кругов. Все числа целые и удовлетворяют следующим ограничениям: 1 ≤ x1, y1, x2, y2, r ≤ 100. Найти суммарную площадь этих кругов с точностью -0.001.
Исходные данные:
1 1 3 1
1
Результаты:
6.283
1.1.2.17. Фонарики-2. Даны два круга. В первых двух строчках содержатся координаты (x1,y1) и (x2,y2) - центры двух кругов. В третьей строке заданы радиусы r1 и r2 описанных выше кругов. Все числа целые и удовлетворяют следующим ограничениям: 1 ≤ x1, y1, x2, y2, r1, r2 ≤ 100. Найти суммарную площадь этих кругов с точностью -0.001.
Исходные данные:
1 1 3 1
1
Результаты:
6.283
1.1.2.18. Ниточка. Злоумышленники варварски вбили в ни в чем не повинную плоскую поверхность Nгвоздей, да так, что только шляпки остались. Мало того, они в своих подлых целях вбили все гвозди в вершины выпуклого многоугольника. После этого они натянули ниточку вокруг всех гвоздей. Вот как примерно они это сделали:
Определить длину этой ниточки. В первой строке входа к этой задаче находятся два числа — количество гвоздей N, 1 ≤N≤ 100, и вещественное числоR— радиус шляпок гвоздей. Все шляпки имеют одинаковый радиус. Далее на входе располагаются ещеNстрок, в каждой из которых записана через пробел пара вещественных координат центра очередного гвоздя; координаты не превосходят по абсолютной величине числа 100. Описания гвоздей приводятся в порядке обхода вершин многоугольника (либо по часовой стрелке, либо против часовой стрелки), начиная с произвольного. Шляпки разных гвоздей не накладываются друг на друга. Вывести вещественное число, округлённое до двух знаков после запятой — длину ниточки, натянутой вокруг всех гвоздей.
Исходные данные:
4 1
0.0 0.0
2.0 0.0
2.0 2.0
0.0 2.0
Результат:
14.28
1.1.2.19. Басня о ларьке. Программисты жили в городе в домах с декартовыми координатами (X[1], Y[1]), (X[2], Y[2]) и (X[3], Y[3]) соответственно. Найти место для пивного ларька так, чтобы сумма расстояний от ларька до каждого из домов будет минимальной. Единственная строка содержит вещественные числа X[1], Y[1], X[2], Y[2], X[3] и Y[3] (-1000 ≤ X[i], Y[i] ≤ 1000). Числа даны не более чем с семью знаками после десятичной точки. Никакие два дома не находятся в одной и той же точке. Вывести через пробел координаты искомого места для ларька таким образом, чтобы сумма расстояний от ларька до каждого из домов совпадала с минимальной с точностью до шести знаков после десятичной точки. Если задача имеет несколько решений, то вывести любое из них.
Исходные данные:
1.1 3.1 5.1 1.1 4.1 5.1
Результат:
3.37423161 3.38281356
Продвинутые задачки.
1.1.3.1. Выпуклый N-угольник P преобразуется в N-угольник Q путём замены середин сторон исходного многоугольника P на вершины многоугольника Q. Требуется по выпуклому N-угольнику Q, заданному координатами вершин, восстановить координаты вершин исходного N-угольника P. Входные данные содержат нечётное число вершин N (3 <= N <= 999), за которым следуют целочисленные координаты xi yi вершин многоугольника Q, перечисленные в порядке обхода по часовой стрелке. Значения координат находятся в диапазоне от –20000 до 20000. Все числа целые и разделены произвольным количеством пробелов и/или символов перевода строки.
Выведите координаты вершин N-угольника P, перечисляя их в порядке обхода по часовой стрелке. При этом первая и вторая вершина должны образовывать сторону, на которой лежит первая вершина N-угольника Q.
Исходные данные:
3 0 0 0 1 1 0
Результат:
1 –1 -1 1 1 1
1.1.3.2. На плоскости дано nточек. Написать программу, которая вычислит и напечатает номера трёх точек, которые образуют треугольник с самой большой площадью. В первой строке задаётся количество точекn, в последующихnстроках задаются пары целых чисел – координаты точек.
Исходные данные:
5
0 0
1 1
2 2
0 2
2 0
Результат:
1 3 5
1.1.3.3. Написать программу для вычисления площади произвольного многоугольника, заданного перечислением пар координат вершин в порядке их обхода по часовой стрелке. Многоугольник не имеет самопересечений. В первой строке задаётся количество вершин n, в последующихnстроках задаются пары целых чисел – координаты вершин. Результат вывести с точностью 2 знака после запятой.
Исходные данные:
5
0 0
0 2
2 2
4 1
4 0
Результат:
7.00
1.1.3.4. На плоскости дано nточек. Написать программу, которая вычислит и напечатает количество равнобедренных треугольников, которые можно составить из заданных точек. В первой строке задаётся количество точекn, в последующихnстроках задаются пары целых чисел – координаты точек.
Исходные данные:
5
0 0
0 2
2 2
4 1
4 0
Результат:
2
1.1.3.5. Написать программу для определения множества точек, которые образуют наименьшую выпуклую оболочку среди заданных nточек на плоскости. В первой строке задаётся количество точекn, в последующихnстроках задаются пары целых чисел – координаты точек. В результат вывести количество точек в первой строке и номера точек, которые образуют найденную оболочку, во второй строке.
Исходные данные:
7
0 0
1 1
0 2
2 2
2 1
4 1
4 0
Результат:
5
1 3 4 6 7
1.1.3.6. Десант. На полигоне установлены радары, которые обнаружат десант, если он будет выброшен ближе чем 0<R<=100000 (целое) м от радара. Полигон представляет собой квадрат размером N на N метров (0<N<=100000 м, целое), юго-западный угол полигона имеет координаты (0; 0), северо-восточный - (N; N). Необходимо найти точку выброса с целыми координатами, так чтобы десант не был обнаружен. Первая строка содержит числа N и R, разделенные пробелом. Вторая строка содержит целое число Z (количество радаров, 0<=Z<=10). Следующие Z строк содержат пары целых чисел X и Y, разделенные пробелом - координаты радаров (0<=X,Y<=N). Вывести целые координаты X и Y точки выброса (разделенные пробелом), либо "НЕТ", если точку выброса найти нельзя.
Исходные данные:
100 10
1
50 50
Результат:
0 0
1.1.3.7. Задача коммивояжёра. Найти кратчайший путь, проходящий через все заданные точки на плоскости. В первой строке задаётся количество вершин n, в последующихnстроках задаются пары целых чисел – координаты точек.
Исходные данные:
Результат:
1.1.3.8. Задача коммивояжёра – 2. Найти кратчайший путь, проходящий через все заданные точки на плоскости и возвращающийся в исходную точку. В первой строке задаётся количество вершин n, в последующихnстроках задаются пары целых чисел – координаты точек.
Исходные данные:
Результат:
1.1.3.9. Задан многоугольник перечислением координат своих вершин в порядке обхода по часовой стрелке. Соединить некоторые вершины этого многоугольника таким образом, чтобы получившийся новый многоугольник был выпуклым, целиком содержался внутри исходного многоугольника и имел наибольшую площадь. В первой строке задаётся количество вершин n, в последующихnстроках задаются пары целых чисел – координаты вершин.
Исходные данные:
Результат:
1.1.3.10. Задан многоугольник перечислением координат своих вершин в порядке обхода по часовой стрелке. Определить и напечатать количество точек с целочисленными координатами, расположенных на сторонах этого многоугольника. В первой строке задаётся количество вершин n, в последующихnстроках задаются пары целых чисел – координаты вершин.
Исходные данные:
Результат:
1.1.3.11. Задан многоугольник перечислением координат своих вершин в порядке обхода по часовой стрелке. Определить, лежит ли заданная точка на периметре этого многоугольника. В первой строке задаётся количество вершин n, в последующихnстроках задаются пары целых чисел – координаты вершин. В последней строке записана пара целых координат отдельной точки.
Исходные данные:
Результат:
1.1.3.12. Вокруг звезды вращаются Nпланет, каждая со своим периодом обращенияTiи углом на начальный момент времениAi. Когда в некоторый момент времени все планеты находятся под одинаковым угломAк звезде, то это явление называется парадом планет. Определить время наступления ближайшего парада планет.
Исходные данные:
Результат:
1.1.3.13. найти точку на плоскости, сумма расстояний до которой от К заданных точек будет наименьшей.
Исходные данные:
Результат:
1.1.3.14. Даны координаты 4-х точек в пространстве (Х1,Y1,Z1), (Х2,Y2,Z2), (Х3,Y3,Z3) , (Х4,Y4,Z4). Определить, лежат ли они в одной плоскости. Если лежат – напечатать «ДА», иначе напечатать «НЕТ». В 4-х строках исходных данных находятся по 3 целых числа – координаты каждой точки.
Исходные данные:
Результат:
1.1.3.15. Дан произвольный многоугольник и точка. Все координаты целые числа. Напечатать «ДА», если точка внутри этого многоугольника. В противном случае напечатать «НЕТ».
Исходные данные:
Результат:
1.1.3.16. Точки в многоугольнике. Задан некоторый многоугольник перечислением координат своих вершин. Определить число точек (и м.б. перечислить их все) с целочисленными координатами, лежащих внутри этого многоугольника.
Исходные данные:
Результат:
1.1.3.17. Вычислить площадь фигуры, ограниченной отрезками прямых линий и дугами окружностей. В первой строке записано одно натуральное число n – количество вершин криволинейного многоугольника. В каждой из следующих n строк описан очередной отрезок или дуга окружности. Для отрезка в строке записаны координаты вершины и один символ +, для дуги сначала записаны координаты вершины, потом записан символ -, потом через пробел 3 целых числа – координаты центра окружности и радиус со знаком. Если радиус положительный – дуга от этой вершины к следующей идёт по часовой стрелке, если отрицательный – против часовой стрелки.
Исходные данные:
Результат:
1.1.3.18. Найти точку на прямой, сумма расстояний до которой от заданных точек будет наименьшей. В первой строке задаётся количество точек n, в последующихnстроках задаются пары целых чисел – координаты точек. В последней строке данных коэффициенты А, В, С уравнения прямойAX+BY+C= 0. Координаты найденной точки напечатать с точностью 3 знака после запятой.
Исходные данные:
Результат:
1.1.3.19. На плоскости дано nточек, образующие последовательные вершины многоугольника в порядке их перечисления. Написать программу, которая определит и напечатает «ДА», если эти точки образуют правильный многоугольник. В первой строке задаётся количество точекn, в последующихnстроках задаются пары целых чисел – координаты точек.
Исходные данные:
4
0 0
0 1
1 1
1 0
Результат:
ДА
1.1.3.20. Дуга на сфере. На поверхности планеты, являющейся шаром радиусом R, заданы две точки своими широтой и долготой. Требуется найти минимальную длину пути по поверхности этой планеты из одной точки в другую. В первой строке находится число R, во второй строке заданы широта и долгота первой точки, в третьей строке - широта и долгота второй точки. Широта измеряется в градусах от -90 до 90, долгота – в градусах от -180 до 180. Радиус R меняется в пределах от 100 до 10000. Все числа вещественные. Вывести длину пути с двумя знаками после запятой.
Исходные данные:
4000 45 120 0 120
Результат:
3141.59
1.1.3.21. Даны Nточек на плоскости и треугольник. Написать программу, которая найдет среди этих точек такие, которые образуют прямоугольник, равновеликий данному треугольнику.
Исходные данные:
Результат:
1.1.3.22. Даны Nточек на плоскости, которые являются последовательными вершинами выпуклого многоугольника. Написать программу нахождения всех четверок точек, которые образуют равнобедренную трапецию.
Исходные данные:
Результат: