Задан прямоугольник. Стороны прямоугольника параллельны осям координат, а две противоположные вершины расположены в точках (x1, y1) и (x2, y2). Задана окружность с центром в точке (x3, y3) и радиусом r. Нужно найти сколько точок лежат в прямоугольнике и окружносте одновременно.
Ограничения: Целые числа 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).
Семпл:
Input:
0 0 5 4 \прямоугольник
4 0 3 \окружнось
Output:
14
Как её решить?
Приложите, пожалуйста, источник задачи.
С помощью головы и образного мышления. Иначе никак. ИМХО, очень вредно просить/давать готовое решение на подобные задачи.
UPD. Полезно в ходе творческого процесса немного порисовать на листе бумаги в клетку.
Источник: http://acmp.ru/index.asp?main=task&id_task=531 Я пробовал решать перебором, но у меня получается Таймлимит. Я не стал бы писать сюда, если б не просидел над ней 2 дня.
Если перебор вообще всех точек, попадающих в ответ, занимает слишком много времени, подумайте какие точки можно закидывать в ответ скопом. На этот вопрос можно найти разные ответы, один из очевидных будет давать решение сложности O(|Y2 — Y1|), чего уже вполне достаточно скорее всего, чтобы получить АС.
А какая ещё может быть сложность? Оо
Неужто за константу/логарифм какой-нибудь считать можно?
А думал закидать так некоторые группы точек. Но увы не получилось.
автор, знаешь что такое бинпоиск???
Эм, это не задача на бинпоиск.
SlavaSSU если Ты это про меня, то нет. Не знаю и не слышал.
а. тогда хз. я просто бинпоиском знаю как решать. по-другому не знаю.
Ты можешь описать идею решения в общих чертах?
Ну, не про эту задачу, а вообще почитай про двоичный поиск — http://bit.ly/1m77FGc
Несложная, но полезная вещь
Я согласен вещь полезная, но можно покинуть задачку, что-бы её можно было бы решить этим методом. Желательно не очень сложною.
Ну, можно эту
http://informatics.msk.ru/mod/statements/view3.php?id=192&chapterid=4#1
переберем y-координату и посчитаем сколько общих точек у круга и прямоугольника находятся на этой высоте. в конце просуммируем ответы для всех высот и это и будет ответ. так вот зафиксировав высоту, можно бинпоиском найти самую левую точку — Lx, которая еще принадлежит окружности, и потом бинпоиском самую правую точку, которая принадлежит окружности — Rx. ответ для этой высоты == Rx — Lx + 1. все. ну еще высоту надо перебирать от минимальной y-координаты прямоугольника до максимальной
А можно найти крайнее точки через формулу окружности ( (x3 — x)^2 + (y3 — y)^2 <= r^2 ) ?
Программисты решают геометрию только бин поиском, формулы не выводят в принципе.
Здесь стоит писать в духе "я решаю геометрию только бинпоиском, формулы не вывожу в принципе".
Ну я, продумывая это решение, прикинул, что мне лично будет проще вывести формулу, чем писать бинпоиск. А комментарий я написал такой только из-за предложения использовать бинпоиск выше. Если бы поставил смайлик было бы понятнее, что это шутка, наверное, но я стараюсь так не делать.
То есть, про закон По ты знаешь. Каков хитрец.
Да, знаю. Теперь :-) Спасибо за информацию.
А кто/что Вам мешает взять и попробовать? :)
Мне в голову пришло простое решение. Переберем x координату точек, которые могут быть в ответе. Перебирать надо от х1 до х2 (иначе точки не лежат в прямоугольнике). Условие того, что точка лежит в окружности — (x3 — x)^2 + (y3 — y)^2 <= r^2. Так как х зафиксирован, то можно преобразовать это неравенство относительно у, далее пересекаем его с у1 < y < y2 и считаем количество точек. То есть, если итоговое пересечение выглядит как l <= y <= r, и r >= l, то в ответ добавляется r — l + 1.
UPD: Кстати говоря, удобный прием: в данной ситуации, чтобы не влезать в квадратное неравенство удобно сдвинуть центр координат в центр окружности.
Я извиняюсь, но я не могу понять откуда взялись l i r? За что они отвечают?
Если считать, что мы уже сдвинули центр координат в центр окружности, то неравенство для окружность выглядит теперь так: x^2 + y^2 <= r^2. Отсюда можно ограничить y. Также есть ограничение, что y1 <= y <= y2. Получается, что у нас два неравенства. Кидаем их в систему и решаем (простая математика). Так вот l и r — это границы итоговой системы — решенной.
Большое спасибо за идею!!! А я дурак брал полный перебор...
Это вторая задача регионального этапа школьников по информатике 2009 года ( разбор(в архиве), информатикс )
Какой позор... Я не сумел решить задачу регионального этапа.