Задача взята с сайта e-olymp.com.
Условие
Определить количество точек пересечения двух окружностей.
Входные данные:
Шесть чисел: $x_1$, $y_1$, $r_1$, $x_2$, $y_2$, $r_2$, где $x_1$, $y_1$, $x_2$, $y_2$ — координаты центров окружностей, а $r_1$, $r_2$ — их радиусы. Все числа — действительные, не превышают $10^9$, заданы не более чем с тремя знаками после запятой.
Выходные данные:
Количество точек пересечения. Если точек пересечения бесконечно много, то вывести $-1$.
Тесты:
$X_1$ | $Y_1$ | $R_1$ | $X_2$ | $Y_2$ | $R_2$ | $N$ |
0 | 0 | 5 | 5 | 0 | 1 | 2 |
0 | 0 | 5 | 0 | 0 | 6 | 0 |
0 | 1 | 6 | 0 | 3 | 6 | 2 |
Код на Haxe:
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
class Test { public var x1:Float; public var y1:Float; public var r1:Float; public var x2:Float; public var y2:Float; public var r2:Float; public function new(x1,y1,r1,x2,y2,r2) { this.x1 = x1; this.y1 = y1; this.r1 = r1; this.x2 = x2; this.y2 = y2; this.r2 = r2; } static function main() { var tests = new Array(); tests.push(new Test(0, 0, 5, 5, 0, 1)); tests.push(new Test(0, 0, 5, 0, 0, 6)); tests.push(new Test(0, 1, 6, 0, 3, 6)); var i:Test; for (i in tests) { var x1:Float = i.x1; var y1:Float = i.y1; var r1:Float = i.r1; var x2:Float = i.x2; var y2:Float = i.y2; var r2:Float = i.r2; var range_sqr:Float = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); var rads_sqr:Float = (r1 + r2) * (r1 + r2); var D:Int; if (range_sqr == 0 && r1 == r2) { D = -1; } else if (range_sqr == rads_sqr || range_sqr == (r2 - r1) * (r2 - r1) || range_sqr == (r1 - r2) * (r1 - r2)) { D = 1; } else if ((range_sqr > rads_sqr) || ((range_sqr < rads_sqr) && ((range_sqr < r1 * r1 / 4 && range_sqr < (r1 - r2) * (r1 - r2)) || (range_sqr < r2 * r2 / 4 && range_sqr < (r2 - r1) * (r2 - r1))))) { D = 0; } else { D = 2; } trace(D); } } } |
Ход решения:
Высчитываем расстояние между центрами окружностей по формуле: $Range = \sqrt{(X_2-X_1)^2+(Y_2-Y_1)^2}$ (храниться и обрабатываться оно будет в квадрате). Вычисление в одну строку:
32 |
var range_sqr:Float = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); |
Далее рассчитываем сумму радиусов окружностей (также в квадрате).
Если центры совпадают ($Range = 0$) и длины радиусов равны, значит, совпадают и окружности:
36 37 38 |
if (range_sqr == 0 && r1 == r2) { D = -1; } |
Если расстояние между окружностями равно сумме радиусов, окружности имеют одну общую точку, касаясь друг друга снаружи. Также одна из окружностей может лежать внутри другой и касаться ее изнутри:
39 40 41 |
else if (range_sqr == rads_sqr || range_sqr == (r2 - r1) * (r2 - r1) || range_sqr == (r1 - r2) * (r1 - r2)) { D = 1; } |
Если расстояние между окружностями превышает сумму радиусов, это значит, что они не пересекаются. Также одна окружность может лежать внутри другой, но не касаться ее:
42 43 44 |
else if ((range_sqr > rads_sqr) || ((range_sqr < rads_sqr) && ((range_sqr < r1 * r1 / 4 && range_sqr < (r1 - r2) * (r1 - r2)) || (range_sqr < r2 * r2 / 4 && range_sqr < (r2 - r1) * (r2 - r1))))) { D = 0; } |
В остальных случаях окружности пересекаются и имеют две общие точки:
45 46 47 |
else { D = 2; } |
Примечание: Входные данные для тестирования были заданы программно из-за определенных затруднений в использовании стандартного ввода в онлайн-среде try.haxe.org.
Ссылки:
Рабочий код для тестирования на try.haxe.org: Try Haxe !
- e-olimp 3966. An ardent collector of butterflies - 13.06.2017
- e-olymp 1078. The line degree - 12.06.2017
- A704 - 11.06.2017
— х1 и прочие математические обозначения, то их нужно оформить через latex — $ x_{1}.
— Вычисление квадратного корня выполняется с погрешностью, которая не позволит в ряде случаев (почти всегда) определить касание окружностей. Думаю, можно подобрать значения при которых пересекающиеся окружности будут определяться как не имеющие общих точек или наоборот. Слабые тесты на сайте e-olymp пропустит такое решение, но то что простительно на первом курсе уже не допустимо для профессионала. Почему не сравнивать квадраты?
— «…затруднений при использовании стандартного ввода» Имеется в виду онлайн среда try.haxe.org? Тогда лучше это указать.
Исправил.
Ну, не совсем, но я уже сам поправил.
Пожалуйста, вставьте все формулы так, как они вставлены в условии задачи, а не генерацией картинок.
Исправил.