Реши задачу на C++: Фермер Иван с юности следит за своим газоном. Газон можно считать…
- User
Реши задачу на C++:
Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы.
В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x1, y1) и (x2, y2). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены.
Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x3, y3) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x3, y3) не превышало r.
Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье?
Требуется написать программу, которая позволит дать ответ на вопрос Ивана.
Входные данные
Первая строка входного файла INPUT.TXT содержит четыре целых числа x1, y1, x2, y2 (−100 000 ≤ x1 < x2 ≤ 100 000; −100 000 ≤ y1 < y2 ≤ 100 000). Во второй строке записаны три целых числа x3, y3, r (−100 000 ≤ x3, y3 ≤ 100 000; 1 ≤ r ≤ 100 000)
Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести одно целое число – число пучков травы, которые были и пострижены, и политы.
- Assistant
Чтобы решить задачу, нам нужно подсчитать количество целочисленных точек, которые одновременно находятся внутри заданного прямоугольника и круга.
Шаги решения:
-
Определение границ X:
Для каждого целого значенияxв интервале отmax(x1, x3 - r)доmin(x2, x3 + r):- Вычисляем
dx = x - x3. - Вычисляем максимальное значение
dy, такое что(dx)^2 + (dy)^2 ≤ r^2. Это дает нам границы дляy.
- Вычисляем
-
Определение границ Y:
- Находим
y_min = max(y1, y3 - dy_max). - Находим
y_max = min(y2, y3 + dy_max). - Количество целых
yв этом диапазоне равноy_max - y_min + 1, еслиy_max >= y_min.
- Находим
-
Подсчет всех возможных точек:
- Суммируем количество таких точек для каждого допустимого
x.
- Суммируем количество таких точек для каждого допустимого
-
Реализация вычисления квадратного корня:
- Используем функцию
std::sqrtдля вычисления целой части квадратного корня, чтобы избежать ошибок округления.
- Используем функцию
Вот реализация этого подхода на C++:
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(0); ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; ll x3, y3, r; cin >> x3 >> y3 >> r; ll count = 0; ll xmin = max(x1, x3 - r); ll xmax = min(x2, x3 + r); for(ll x = xmin; x <= xmax; x++){ ll dx = x - x3; ll dy_sq = (ll)r * r - (ll)dx * dx; if(dy_sq < 0) continue; // Compute floor(sqrt(dy_sq)) ll dy_max = floor(sqrt((long double)dy_sq)); ll ymin = max(y1, y3 - dy_max); ll ymax = min(y2, y3 + dy_max); if(ymax >= ymin){ count += (ymax - ymin + 1); } } cout << count; }Пояснения:
-
Ввод данных:
Считываем координаты прямоугольника(x1, y1)и(x2, y2), а также параметры круга(x3, y3, r). -
Основной цикл:
Проходим по всем возможнымxв пределах отmax(x1, x3 - r)доmin(x2, x3 + r). Для каждого такогоxвычисляем максимально возможное значениеdy(разница поy), которое позволяет точке(x, y)быть внутри круга. -
Подсчет допустимых
y:
Находим минимальное и максимальное значениеy, удовлетворяющие как условиям прямоугольника, так и круга. Разность этих значений плюс один дает количество допустимых точек для текущегоx. -
Вывод результата:
После завершения цикла выводим общее количество точек, удовлетворяющих обоим условиям.
Этот алгоритм эффективно решает задачу за время
O(xmax - xmin), что в данном случае допустимо, так как диапазонxограничен значениями-100000до100000. -