Задача
На плоскости задана система концентрических окружностей, центры которых находятся в начале координат, а радиусы равны $1,2,3\dots.$ Также на плоскости задан отрезок, концы которого находятся в точках $(X_{1}, Y_{1})$ и $(X_{2}, Y_{2}).$ Необходимо найти число общих точек этого отрезка и указанной системы окружностей.
Входные данные
Первая строка входного файла содержит 4 целых числа $X_{1}, Y_{1}, X_{2}, Y_{2}.$ Эти числа не превосходят $10^{3}$ по абсолютной величине. Заданный отрезок имеет ненулевую длину.
Выходные данные
В выходной файл выведите ответ на задачу.
Тесты
| Входные данные | Выходные данные |
| -1 -1 1 1 | 2 |
| -1 1 1 1 | 1 |
| 1 1 2 1 | 1 |
| -5 -5 5 -5 | 5 |
| -10 10 -10 10 | 28 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main(String[] args) throws java.lang.Exception { final double e = 10e-8; Scanner in = new Scanner(System.in); double x1, y1, x2, y2; x1 = in .nextDouble(); y1 = in .nextDouble(); x2 = in .nextDouble(); y2 = in .nextDouble(); double d, a, b; d = Math.abs((y2 * x1 - x2 * y1) / Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))); //Растояние до точки на отрезке, ближайщей к началу координат a = Math.sqrt(x1 * x1 + y1 * y1); //Растояние от начала координат до первой точки b = Math.sqrt(x2 * x2 + y2 * y2); //Растояние от начала координат до второй точки int count = 0; if ((2 * x1 * x1 - 2 * x1 * x2 + 2 * y1 * y1 - 2 * y1 * y2 < 0) | (2 * x2 * x2 - 2 * x1 * x2 + 2 * y2 * y2 - 2 * y1 * y2 < 0)) //проверка первого условия count = (int)(Math.max(a, b) + e) - (int)(Math.min(a, b) - e); else { //второе условие count = (int)(a + e) - (int)(d - e); count = count + (int)(b + e) - (int)(d - e); if ((Math.abs(Math.round(d) - d) < e) & (Math.abs(d) > e)) { //проверка крайнего случая count--; } } System.out.print(count); } } |
Решение
Для начала рассмотрим первое условие. Пусть наш отрезок таков, что при движении от одного края к другому, расстояние до начала координат возрастает. Для такого отрезка ответ очевиден — это количество целых чисел между расстояниями от начала координат до обоих концов отрезка. Условие из шестнадцатой строчки кода получилось путем приведения подобных и раскрытия скобок следующих неравенств: $x_{1}^{2}+y_{1}^{2}-x_{2}^{2}-y_{2}^{2}+(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}<0$ и $-x_{1}^{2}-y_{1}^{2}+x_{2}^{2}+y_{2}^{2}+(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}<0.$
Иначе сведем данную задачу к рассмотренной выше. Для этого необходимо найти на отрезке точку, ближайшую к началу координат. Таким образом исходный отрезок разбивается на два новых, для которых выполнено условие из простой задачи. Также следует рассмотреть крайний случай, а именно, если ближайшая к $(0,0)$ точка находится на целом расстоянии от начала координат. В этом случае мы посчитаем это пересечение дважды, поэтому необходимо уменьшить ответ на единицу.
Стоит заметить, что находить саму ближайшую точку нет необходимости. Достаточно найти лишь расстояние до нее. Также мы добавляем маленькую константу
$\varepsilon = 10^{-8}$ к большему расстоянию до конца отрезка и отнимаем из меньшего, чтобы избежать случая нахождения какой-либо точки отрезка на окружности. В противном случае решение задачи будет работать не корректно.