Морской бой
Вы разрабатываете игру “Морской бой”. В самом начале каждый игрок расставляет несколько кораблей на поле в определённых позициях. Каждый корабль располагается по прямой линии от до , при этом соединяющая их линия всегда перпендикулярна краям сетки.
На первом этапе вы хотите проверить игровое поле, чтобы убедиться, что пользователи не ставят корабли слишком близко друг к другу или не пересекают их. Между каждым кораблём и любым другим кораблём должна быть хотя бы одна клетка воды. Разрешается ставить корабли вплотную к границе, без дополнительного зазора между бортом корабля и краем поля.
Входные данные
Первая строка входных данных содержит 3 целых числа:
n — количество кораблей (1 ≤ n ≤ 20), w — ширина поля боя (1 ≤ w ≤ 1000) и h — высота поля боя (1 ≤ h ≤ 1000).В следующих
n строках содержится по 4 целых числа — и (1 ≤ ≤ ≤ h, 1 ≤ ≤ ≤ w) — координаты каждого корабля.Выходные данные
Программа должна вывести
Valid, если расположение кораблей корректно, или Invalid — в противном случае.Примеры
Входные данные | Выходные данные |
2 10 10
1 1 1 5
8 1 8 10 | Valid |
2 10 10
1 1 1 5
2 3 2 10 | Invalid |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB