Задача №114763. Прожекторы
На координатной плоскости расположено прямоугольное поле с углами в точках \((0, 0)\), \((w, 0)\), \((w, h)\) и \((0, h)\). На поле расположены \(n\) прожекторов, \(i\)-й прожектор находится в точке с координатами \((x_i, y_i)\).
Каждый из прожекторов освещает угол в \(90^{\circ}\), со сторонами параллельными осям координат, с вершиной в своей позиции. Таким образом, есть четыре возможных направления угла, который может освещать прожектор.
Дано множество разрешенных направлений углов — одинаковое для всех прожекторов. Для каждого прожектора вы можете выбрать одно из разрешенных направлений. Требуется осветить прожекторами наибольшую возможную часть поля. Точка считается освещённой, если ее освещает хотя бы один прожектор.
Вычислите максимальную возможную площадь части поля, которую можно осветить прожекторами, установив каждый из них в одном из разрешенных направлений.
Каждый тест состоит из нескольких наборов входных данных.
В первой строке дано одно целое число \(k\) (\(1 \le k \le 4\)) — число разрешённых направлений углов прожекторов для всех наборов входных данных теста. Во второй строке даны \(k\) целых чисел — номера разрешённых направлений. Все \(k\) чисел различны и перечислены в порядке возрастания.
Во третьей строке дано одно целое число \(t\) (\(1 \le t \le 10\,000\)) — количество наборов входных данных. Далее следуют описания наборов входных данных.
В первой строке каждого набора даны три целых числа \(n\), \(w\) и \(h\) (\(1 \le n \le 100\,000\); \(1 \le w, h \le 10^9\)) — количество прожекторов на поле и размеры поля.
В следующих \(n\) строках даны по два целых числа \(x_i\) и \(y_i\) (\(0 \le x_i \le w\), \(0 \le y_i \le h\)) — координаты точки, в которой расположен \(i\)-й прожектор. Гарантируется, что никакие два прожектора не находятся в одной точке.
Для каждого набора входных данных выведите одно целое число — максимальную площадь части поля, которую можно осветить прожекторами.
Обозначим суммарное количество прожекторов во всех наборах входных данных за \(\sum n\).
| Ограничения | |||||
| Подзадача | Баллы | Разрешенные направления | \(\sum n\) | Необх. подзадачи | Информация о проверке |
| 1 | 13 | Разрешено только направление \(1\) | \(\sum n \le 10^5\) | первая ошибка | |
| 2 | 11 | Разрешены направления \(1\) и \(2\) | \(\sum n \le 5000\) | первая ошибка | |
| 3 | 14 | \(\sum n \le 10^5\) | 2 | первая ошибка | |
| 4 | 10 | Разрешены направления \(1\) и \(3\) | \(\sum n \le 100\) | первая ошибка | |
| 5 | 12 | \(\sum n \le 5000\) | 4 | первая ошибка | |
| 6 | 14 | \(\sum n \le 10^5\) | 4, 5 | первая ошибка | |
| 7 | 7 | Разрешены направления \(1\), \(2\) и \(3\) | \(\sum n \le 100\) | первая ошибка | |
| 8 | 8 | \(\sum n \le 2000\) | 7 | первая ошибка | |
| 9 | 11 | Разрешены направления \(1\), \(2\), \(3\) и \(4\) | \(\sum n \le 10^5\) | первая ошибка | |
1 1 1 4 6 4 3 3 1 2 4 1 5 0
13
2 1 2 1 4 9 7 3 0 0 5 4 4 1 2
55
2 1 3 1 5 6 11 4 2 2 7 1 10 3 8 5 4
57
3 1 2 3 1 5 7 10 1 9 5 5 3 4 2 6 4 3
63
4 1 2 3 4 1 3 8 6 2 2 4 5 6 1
44