Задача
Василий и Петр игрались на уроке. На прямоугольном листке бумаги в клеточку Василий по линях сетки рисует отрезок, параллельный одной из сторон листка, и рамку прямоугольной формы. Он шепчет на ухо Петру координаты концов отрезка и координаты двух противоположных углов рамки, а Петр старается быстро определить длину части отрезка, оказавшуюся внутри рамки. У него это плохо получалось, и он написал программу, которая это делала всегда правильно. Напишите её и вы.
Входные данные
Заданы через пробел $8$ чисел — координаты начала и конца отрезка и координаты противоположных углов рамки. Координаты — целые числа, не превышающие по модулю $35000$.
Выходные данные
Вывести одно число — длину части отрезка, которая оказалась внутри рамки.
Тесты
№ |
Входные данные |
Выходные данные |
| 1 | 4 1 9 1 2 3 5 -2 | 1 |
| 2 | 2 2 6 2 4 4 7 1 | 2 |
| 3 | 3 2 3 5 4 3 6 2 | 0 |
| 4 | 1 2 5 2 2 5 4 1 | 2 |
Код программы
|
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 |
class Main { static int distance(int a, int b, int c, int d) { int ans = 0; if (a > b) { int temp = a; a = b; b = temp; } if (c > d) { int temp = c; c = d; d = temp; } if (b < c || a > d) { ans = 0; } else { int l = 0, r = 0; l = Math.max(a, c); r = Math.min(b, d); ans = r - l; } return ans; } public static void main (String[] args) { java.util.Scanner in = new java.util.Scanner(System.in); int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt(); int x3 = in.nextInt(), y3 = in.nextInt(), x4 = in.nextInt(), y4 = in.nextInt(); if (x1 != x2) { System.out.println(y1 < Math.max(y3, y4) && y1 > Math.min(y3, y4) ? distance(x1, x2, x3, x4) : 0); } else { System.out.println(x1 < Math.max(x3, x4) && x1 > Math.min(x3, x4) ? distance(y1, y2, y3, y4) : 0); } } } |
Решение
Так как отрезок параллелен одной из сторон листка, то абсциссы (или ординаты) концов отрезка должны совпадать. Будем рассматривать случай когда они находятся между абсциссами (или ординатами соответственно) соответствующих вершин прямоугольника (в противном случае отрезок не проходит через рамку и ответ $0$).
Если абсцисса левого или правого конца отрезка будет находиться, соответственно, правее крайней справа или левее крайней слева абсциссы вершины прямоугольника, то отрезок не проходит через рамку (для ординат аналогично).
В противном случае, отрезок проходит через рамку и мы можем подсчитать какая его часть находится внутри рамки. Для этого необходимо найти разность между абсциссами (ординатами) концов части отрезка находящийся внутри прямоугольника. Абсциссой левого конца такого отрезка будет максимальная из абсцисс левого конца изначального отрезка и крайней слева абсциссы прямоугольника, абсциссой правого конца такого отрезка будет минимальная из абсцисс правого конца изначального отрезка и крайней справа абсциссы прямоугольника (для ординат аналогично).
Обозначим искомую длину как $ans$, тогда $ans = min(x_{2}, x_{4})-max(x_{1}, x_{3})$.
Для ординат $ans = min(y_{2}, y_{4})-max(y_{1}, y_{3})$.
Ссылки
Условие задачи на e-olymp
Код программы на ideone