Защита королевства
Теодор реализует новую стратегию игры «Оборона Царства». На каждом уровне игрок защищает королевство, которое представлено прямоугольной сеткой ячеек. В некоторых клетках игрок строит арбалетные башни. Башня защищает все клетки в той же строке и том же столбце. Никакие две башни не находятся на одной строке или столбце.
Штрафом положения является количество клеток в крупнейшем незащищенном прямоугольнике. Например, положение, показанное на рисунке имеет штраф [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 |
#include <iostream> #include <algorithm> using namespace std; int main() { int x_max, y_max, n, a=0, b=0; cin>>x_max>>y_max>>n; int *x=new int[n+2]; int *y=new int[n+2]; for(int i=1;i<n+1;i++) cin>>x[i]>>y[i]; x[0] = y[0] = 0; x[n+1] = x_max + 1; y[n+1] = y_max + 1; sort(x, x + n+1); sort(y, y + n+1); 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]; } cout<<(a-1)*(b-1); return 0; } |
Решение задачи:
Алгоритм решения задачи состоит в том, чтобы найти максимальное количество незащищенных клеток между соседними башнями по координатам абсцисс и ординат (которые будет на [latex]1[/latex] меньше чем сама разность координат) и перемножить полученные числа тем самым найдя площадь образованного ими прямоугольника.
Для решения данной задачи нужно создать два массива в [latex]x[/latex] и [latex]y[/latex] (в первом будут находится [latex]x_i[/latex] координаты, а во втором [latex]y_i[/latex]) размера на [latex]2[/latex] больше чем количество заданных башен, так как нужно учитывать рамки поля, для чего достаточно добавить две башни c координатами [latex]\left(0;0\right)[/latex] и [latex]\left(x_{max}+1; y_{max}+1\right).[/latex] Далее нужно отсортировать эти массивы и найти максимальную разность между соседними элементами ([latex]a[/latex] — максимальная разность между [latex]x_i[/latex] элементами, [latex]b[/latex] — максимальная разность между [latex]y_i[/latex]). Далее, по формуле [latex]\left(a-1\right)\cdot\left(b-1\right)[/latex] находим площадь самого большого незащищенного прямоугольника, которая равна количеству клеток в нем, что и является ответом задачи.