Світський прийом#9061

Світський прийом (Розбір)

Джонні Інгліш і Боф досягають кінцевої точки одночасно за час $t$ . Джонні Інгліш долає відстань $s_{1} = p \cdot t$ s_1 = p \cdot t, а Боф $s_{2} = q \cdot t$ s_2 = q \cdot t. Співвідношення пройдених відстаней дорівнює співвідношенню швидкостей: $s_{1} / s_{2} = p / q$ s_1 / s_2 = p / q.

Побудуємо такі шляхи конструктивно. Розглянемо, наприклад, маршрут з $4$ точок: $(0, 0) \to (2 q, 0) \to (2 q, p - q) \to (2 q, 0)$ (0, 0) → (2q, 0) → (2q, p - q) → (2q, 0). Тут обрано координату $p - q$ p - q, щоб її значення було невід’ємним (за умовою задачі $q \leq p$ q \le p).

Довжина шляху Джонні Інгліша дорівнює $2 q + 2 * (p - q) = 2 p$ 2q + 2 * (p - q) = 2p.
Довжина шляху Бофа дорівнює $2 q$ .

Якщо швидкості Джонні Інгліша і Бофа однакові, то точки $(2 q, 0)$ (2q, 0) і $(2 q, p - q)$ (2q, p - q) збігаються, а за умовою задачі на маршруті не може бути двох однакових точок підряд. У такому разі як рішення можна обрати, наприклад, наступний маршрут: $(0, 0) \to (1, 0)$ (0, 0) → (1, 0).

Реалізація алгоритму

Зчитуємо вхідні дані.

scanf("%d %d", &q, &p);

Якщо швидкості Джонні Інгліша і Бофа однакові, то вони рухаються з точки $(0, 0)$ у точку $(1, 1)$ .

if (q == p)
{
  printf("2\n");
  printf("%d %d\n", 0, 0);
  printf("%d %d\n", 1, 0);
  return 0;
}

C++

Якщо $p \neq = q$ p \ne q, то маршрут складається з чотирьох точок.

printf("4\n");
printf("%d %d\n", 0, 0);
printf("%d %d\n", 2 * q, 0);
printf("%d %d\n", 2 * q, p - q);
printf("%d %d\n", 2 * q, 0);