Защита королевства
Теодор реализует новую стратегию игры «Оборона Царства». На каждом уровне игрок защищает королевство, которое представлено прямоугольной сеткой ячеек. В некоторых клетках игрок строит арбалетные башни. Башня защищает все клетки в той же строке и том же столбце. Никакие две башни не находятся на одной строке или столбце.
Штрафом положения является количество клеток в крупнейшем незащищенном прямоугольнике. Например, положение, показанное на рисунке имеет штраф [latex]12[/latex].
Помогите Теодору написать программу, вычисляющую штраф в заданной позиции.
Входные данные:
Первая строка содержит три целых числа: [latex]w[/latex] — ширина сетки, [latex]h[/latex] — высота сетки и [latex]n[/latex] — количество арбалетных башен [latex](1 ≤ w, h ≤ 40000; 0 ≤ n ≤ min(w, h))[/latex].
Каждая из следующих n строк содержит два целых числа [latex]x_i[/latex] и [latex] y_i[/latex] — координаты клетки с башней [latex](1 ≤ x_i ≤ w; 1 ≤ y_i ≤ h)[/latex].
Выходные данные:
Вывести одно число — количество клеток в наибольшем прямоугольнике, не защищенном башнями.
Тесты
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
|---|---|---|
| 1 | 10 10 3
1 1 2 2 3 3 |
49 |
| 2 | 15 15 4
4 4 5 5 7 8 13 15 |
30 |
| 3 | 30 30 5
13 14 16 27 29 30 5 5 10 15 |
132 |
| 4 | 100 100 2
1 1 100 100 |
9604 |
| 5 | 3 3 3
1 1 2 2 3 3 |
0 |
Код программы:
|
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 |
import java.util.*; import java.lang.*; import java.util.Arrays.*; class Main { public static void main (String[] args) { int a = 0, b = 0; Scanner input = new Scanner(System.in); int x_max = input.nextInt(); int y_max = input.nextInt(); int n = input.nextInt(); int x[] = new int[n+2]; int y[] = new int[n+2]; for(int i = 1; i < n + 1; i++) { x[i] = input.nextInt(); y[i] = input.nextInt(); } x[0] = y[0] = 0; x[n + 1] = x_max + 1; y[n + 1] = y_max + 1; Arrays.sort(x); Arrays.sort(y); for(int i = 0; i < n + 1; i++) { if(x[i + 1]-x[i]>a) a = x[i + 1]-x[i]; if(y[i + 1]-y[i]>b) b = y[i + 1]-y[i]; } System.out.print((a-1)*(b-1)); } } |
Решение задачи:
Алгоритм решения задачи состоит в том, чтобы найти максимальное количество незащищенных клеток между соседними башнями по координатам абсцисс и ординат (которые будет на [latex]1[/latex] меньше чем сама разность координат) и перемножить полученные числа тем самым найдя площадь образованного ими прямоугольника.
Для решения данной задачи нужно создать два массива в [latex]x[/latex] и [latex]y[/latex] (в первом будут находится [latex]x_i[/latex] координаты, а во втором [latex]y_i[/latex]) размера на [latex]2[/latex] больше чем количество заданных башен, так как нужно учитывать рамки поля, для чего достаточно добавить две башни c координатами ([latex]0[/latex];[latex]0[/latex]) и ([latex]x[/latex] [latex]max+1[/latex]; [latex]y[/latex] [latex]max+1[/latex]). Далее нужно отсортировать эти массивы и найти максимальную разность между соседними элементами ([latex]a[/latex] — максимальная разность между [latex]x_i[/latex] элементами, [latex]b[/latex] — максимальная разность между [latex]y_i[/latex]). Далее, по формуле [latex](a-1)\cdot(b-1)[/latex] находим площадь самого большого незащищенного прямоугольника, которая равна количеству клеток в нем, что и является ответом задачи.