Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- <?php
- /*
- Нахождение формулы решения.
- Пусть у нас есть N точек на одной прямой и M - на другой.
- отрезок Отр_N1_M1 не пересекается ни с какими отрезками вообще,
- отрезок Отр_N1_M2 пересекается (N - 1) раз (все отрезки от точек N2 до NN в точку M1)
- отрезок Отр_N1_M3 пересекается 2 * (N - 1) раз (все отрезки от точек N2 до NN в 2 точки на
- противоположной стороне - M1 и M2).
- И так далее.
- Таким образом, сумма точек пересечения всех отрезков, выходящих из точки N1 равна:
- (N - 1) + 2 * (N - 1) + 3 * (N - 1) + .... (M - 1)(N - 1) = (N - 1) * (M * (M - 1) / 2)
- Если обозначить функцию f(n, m) - как требуемый результат для количества точек n и m,
- то
- f(n, m) = (n - 1) * (m * (m - 1) / 2) + f(n - 1, m) [1]
- f(n - 1, m) аналогично разворачивается в:
- f(n - 1, m) = (n - 2) * (m * (m - 1) / 2) + f(n - 2, m)
- Подставляя это выражение в формулу выше [1] и развертывая формулу дальше получаем
- итоговую формулу:
- f(n, m) = (n - 1 + n - 2 + .... + 1) * m * (m - 1) / 2 =
- (n * (n - 1) / 2) * (m * (m - 1) / 2)
- */
- function task103($n, $m) {
- return ($n * ($n - 1) / 2) * ($m * ($m - 1) / 2);
- }
- function test($n, $m) {
- printf("%s, %s => %s\n", $n, $m, task103($n, $m));
- }
- foreach([[2, 3], [1, 1], [1, 2], [2, 2], [1000, 1000]] as $data) {
- test($data[0], $data[1]);
- }
- /** результаты тестов
- 2, 3 => 3
- 1, 1 => 0
- 1, 2 => 0
- 2, 2 => 1
- 1000, 1000 => 249500250000
- */
Add Comment
Please, Sign In to add comment