Некоторые задачи вычислительной геометрии

Задача №195.  Симметрия

Многие из вас, вероятно, знакомы с понятием симметрии относительно прямой. Пусть на плоскости расположена прямая L и точка A. Точка B называется симметричной точке A относительно прямой L, если отрезок АВ перпендикулярен прямой L и делится пополам точкой пересечения с ней. В частности, если точка А лежит на прямой L, то точка B совпадает с точкой А.

Задана прямая L, параллельная одной из осей координат, и точка А. Найдите точку В, симметричную А относительно L.

Входные данные

Первая строка входного файла INPUT.TXT содержит 4 числа: x1, y1, x2, y2 – координаты двух различных точек, через которые проходит прямая L. Вторая строка входного файла содержит 2 числа xA и yA – координаты точки А. Все числа во входном файле целые и не превосходят 108 по модулю.

Выходные данные

В выходной файл OUTPUT.TXT выведите числа xB и yB – координаты точки B.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	0 0 0 1 10 10	-10 10
2	0 0 1 0 10 10	10 -10

Решение

#include<cstdio>

int main() {

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);

int x1, y1, x2, y2, xa, ya;

scanf("%d %d %d %d %d %d", &x1, &y1, &x2, &y2, &xa, &ya);

int x = xa, y = ya;

if (x1 == x2) // OX

   x = 2 * x1 - xa;  

if (y1 == y2) // OY

   y = 2 * y1 - ya;  

printf("%d %d", x, y);

}

Задача №196.  Выпуклая оболочка

(Время: 1 сек. Память: 16 Мб)

Рассмотрим бесконечный лист клетчатой бумаги. Закрасим некоторое множество клеток в черный цвет. Теперь мы хотим закрасить минимальное количество клеток, так, чтобы множество черных клеток стало выпуклым.

Напомним, что геометрическая фигура Φ называется выпуклой, если для любых точек A из Φ и В из Φ с вещественными координатами отрезок [AB] принадлежит Φ.

Входные данные

В первой строке входного файла INPUT.TXT содержатся два числа N и M (1 ≤ N, M ≤ 100) — размеры куска бумаги, куда попали все черные клетки. В каждой из следующих N строк содержится М символов «*» или «.». Символ «*» обозначает черную клетку, а «.» белую.

Выходные данные

В выходной файл OUTPUT.TXT выведите выпуклое множество, содержащее минимальное количество дополнительно покрашенных черных клеток, в ровно N строках по M символов «*» или «.» в каждой.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	2 4 ..*. .**.	.**. .**.
2	4 3 .*. .*. .*. .*.	.*. .*. .*. .*.

Решение

#include<iostream>

usingnamespace std;

int n, m, i, j;

char ch;

int main () {

cin >> n >> m;

int max_x = -1, max_y = -1, min_x = 101, min_y = 101;

for(i = 0; i < n; i++)

   for(j = 0; j < m; j++) {

       cin >> ch;

       if (ch == '*') {

           if (i < min_x) min_x = i;

           if (i > max_x) max_x = i;

           if (j < min_y) min_y = j;

           if (j > max_y) max_y = j;

       }

   }

for(i = 0; i < n; ++i, cout << endl)

   for(j = 0; j < m; ++j)

       cout << (min_x <= i && i <= max_x &&

               min_y <= j && j <= max_y ? '*' : '.');

}

Задача №197.  Проверка треугольника

 

Задача №198.  N-угольное колесо

На одном известном автозаводе страны N-мерики главный инженер-рационализатор внес предложение вместо круглых колес использовать колеса в форме правильных N-угольников. "При этом", — сказал он, "важным показателем качества такого колеса будет разность между радиусом описанной окружности и радиусом вписанной окружности". Причем колесо считается качественным, если его показатель качества меньше единицы.

Задано число N и длина A стороны N-угольного колеса. Необходимо определить: является ли такое колесо качественным.

Входные данные

Входной файл INPUT.TXT содержит два натуральных числа: N и A (3 ≤ N ≤ 1000, 1 ≤ A ≤ 1000).

Выходные данные

В выходной файл OUTPUT.TXT выведите «YES», если это качественное колесо и «NO» в противном случае.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	3 1	YES
2	239 566	NO

Решение

#include<fstream>

#include<cmath>

usingnamespace std;

int main() {

ifstream cin("input.txt");

ifstream cout("output.txt");

int n;

float a;

cin >> n >> a;

float alpha = M_PI/n;

float r = a/(2*sin(alpha));

cout << (r-r*cos(alpha)<1 ? "YES\n" : "NO\n");

}

Задача №199.  Две окружности

На плоскости даны две окружности. Требуется проверить, пересекаются ли они.

Входные данные

Входной файл INPUT.TXT состоит из двух строк. На каждой строке записана информация об одной окружности – координаты ее центра x и y (целые числа, по модулю не превосходящие 5000) и радиус (целое число 1 ≤ r ≤ 1000).

Выходные данные

В выходной файл OUTPUT.TXT выведите «YES», если окружности пересекаются, и «NO» в противном случае.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	0 0 2 0 3 2	YES
2	1 1 1 4 4 1	NO

Решение

#include<iostream>

#include<fstream>

#include<cmath>

usingnamespace std;

main () {

ifstream cin("input.txt");

ofstream cout("output.txt");

double x,y,r,x1,y1,r1,d;

cin >> x >> y >> r >> x1 >> y1 >> r1;

d = sqrt((x-x1)*(x-x1) + (y-y1)*(y-y1));

cout << ((d <= r+r1  && d >= abs(r-r1)) ?"YES" : "NO");

}

Задача №200.  Фонарики (acmp.ru)

 «Одна голова хорошо, а две лучше. Одна лампочка хорошо, а две лучше!» - подумал Миша, и решил собрать фонарик с двумя лампочками. Теперь он хочет узнать, насколько фонарик с двумя лампочками лучше, чем фонарик с одной. Для этого Миша посветил фонариком на стену, и каждая из лампочек осветила на ней круг.

Эффективность фонарика Миша хочет оценить через площадь освещенной части стены. Миша догадался измерить координаты центров освещенных кругов и их радиусы (которые оказались одинаковыми). Причем, площадь, освещаемая фонариком с одной лампочкой известна, т.к. описана в документации, прилагаемой к фонарику. Но что делать дальше он не знает. Напишите программу, которая поможет Мише.

Входные данные

В первых двух строчках содержатся координаты (x₁,y₁) и (x₂,y₂) - центры кругов от лампочек собранного Мишей фонарика. В третьей строке задан радиус r описанных выше кругов, а четвертая строка содержит площадь освещения s фонариком из одной лампочки. Все числа целые и удовлетворяют следующим ограничениям: 1 ≤ x₁,y₁,x₂,y₂,r ≤ 100, 1 ≤ s ≤ 10⁵. Так же заметим, что площади, освещаемые разными фонариками, отличаются друг от друга более чем на 10^-3.

Выходные данные

Выведите «YES», если Мишин фонарик лучше старого (т.е. освещает большую площадь) и «NO» в противном случае.

Примеры

№	Ввод	Вывод
1	1 2 3 4 2 22	YES
2	1 1 100100 1 7	NO

Решение

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

Рис. 34. Иллюстрация к задаче "Фонарики" (acmp.ru)

Очевидно, общая площадь q покрытия двух кругов равна сумме их площадей минус площадь криволинейной фигуры, построенной на дугах P₁P₂ обеих окружностей. Обозначим площадь этой фигуры w. Величина w равна удвоенной площади сектора каждого из кругов и её можно найти по формуле из школьного курса геометрии:

 

Где α – величина угла P₁O₁P₂ (или P₁O₂P₂ , что то же самое) в радианах.

#include <fstream>

#include <cmath>

using namespace std;

int main() {

ifstream cin("input.txt");

ofstream cout("output.txt");

double x1, y1, x2, y2, r, s, l, alpha, p, q, w;

cin >> x1 >> y1 >> x2 >> y2 >> r >> s;

l = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));

alpha = 2 * acos(l / 2 / r);

p = M_PI * r * r;

w = (alpha - sin(alpha)) * r * r;

q = l < r + r ? 2 * p - w : 2 * p;

cout << (q > s ? "YES" : "NO");

}

Задача №201.  Клад (acmp.ru)

(Время: 2 сек. Память: 32 Мб)

Источник задачи: Московская олимпиада по информатике 2002/2003 г.

Найти закопанный пиратами клад просто: всё, что для этого нужно – это карта. Как известно, пираты обычно рисуют карты от руки и описывают алгоритм действий. Большая часть таких действий просто сводится к прохождению какого-то количества шагов в одном из восьми направлений (1 – север, 2 – северо-восток, 3 – восток, 4 – юго-восток, 5 – юг, 6 – юго-запад, 7 – запад, 8 – северо-запад) (см. рис). Длина шага в любом направлении равна 1.

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

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

Входные данные

Первая строка входного файла C.IN содержит число N – число указаний (1≤N≤40). Последующие N строк содержат сами указания – номер направления (целое число от 1 до 8) и количество шагов (целое число от 1 до 1000). Числа разделены пробелами.

Выходные данные

В выходной файл C.OUT выведите координаты X и Y точки (два вещественных числа, разделённые пробелом), где зарыт клад, считая, что ось O_X направлена на восток, а ось O_Y – на север. Вначале кладоискатель должен стоять в начале координат. Координаты необходимо вывести с точностью 10^-3.

Примеры

№	C.IN	C.OUT
1	6 1 3 3 1 1 1 3 3 5 2 7 1	3.000 2.000
2	1 8 10	-7.071 7.071

Решение

#include <fstream>

#include <iomanip>

#include <cmath>

using namespace std;

int n, i, angle, count;

float x, y;

int main(){

ifstream cin("c.in");

ofstream cout("c.out");

cin >> n;

while(n--){

   cin >> angle >> count;

   --angle;

   x += sin(M_PI * angle / 4) * count;

   y += cos(M_PI * angle / 4) * count;

  }

cout << fixed << setprecision(3) << x << ' ' << y;

}

Не во всех компиляторах C++ поддерживается расширение GNU C++ макрос M_PI со значением числа «пи». Нужную нам для вычислений величину p/4 легко найти как arctg1.

#include<cstdio>

#include <cmath>

int n, i, angle, count;

float x, y, p = atan(1);

int main(){

freopen("c.in", "r", stdin);

freopen("c.out", "w", stdout);

scanf("%d", &n);

while(n--){

   scanf("%d%d", &angle, &count);

   --angle;

   x += sin(p * angle) * count;

    y += cos(p * angle) * count;

}

printf("%.3f %.3f", x, y);

}

Задача №202.  Пицца

Пицца – любимое лакомство Васи, он постоянно покупает и с удовольствием употребляет различные сорта этого великолепного блюда. Однажды, в очередной раз, разрезая круглую пиццу на несколько частей, Вася задумался: на какое максимальное количество частей можно разрезать пиццу за N прямых разрезов?

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

Входные данные

Натуральное число N – число прямых разрезов пиццы (N <= 1000).

Выходные данные

Единственное число – искомое количество кусков пиццы.

Примеры

№	Ввод	Вывод
1	2	4
2	3	7

Решение

Рис. 35. Иллюстрация к задаче "Пицца"

[5 p. 21]Две прямые могут пересекаться не более чем в одной точке. Новая прямая с номером n>0 может пересекать n-1 ранее построенных прямых не более чем в n-1 точке. Допустим, что предыдущие n-1 прямых создали L_n-1областей, на которые разделилась пицца.Тогда с учетом новой прямой

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

Легко увидеть, что добавляемые числа nв рекуррентном соотношении образуют арифметическую прогрессию с шагом 1. Тогда

#include <iostream>

using namespace std;

int main(){

int n;

cin >> n;

cout << n*(n+1)/2+1;

}

Задача №203.  Точка и многоугольник

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

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

Решение

Первый шаг – триангуляция. Точка принадлежит выпуклому многоугольнику в том случае, когда она принадлежит одному из треугольников, образованных его вершинами. Чтобы не рассматривать одни и те же треугольники A_iA_jA_kпо несколько раз (A_jA_iAk, A_kA_jA_iи др.), а также исключить «псевдотреугольники» A_iA_kA_i, условимся, что i<j<k

for(int i=1;i<=N-2;i++)

for(int j=i+1; j<=N-1; j++)

     for(int k=j+1; k<=N; k++)

           ... Проверка треугольников с i-ой, j-ой, k-ой вершиной

Рис. 36 Разбиение выпуклого многоугольника на треугольники

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

Задача №204.  Точка и треугольник

С консоли через пробел вводятся 4 пары чисел с плавающей точкой, не превышающих по модулю 100, которые являются координатами точек A₀, A₁, A₂ и A₃соответственно.

Определить, принадлежит ли точка A₀треугольнику A₁A₂A₃.

Решение

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