Багатокутники (Numconv) (юніори+ старша ліга)
Задана клітчаста сітка. Скільки різних опуклих багатокутників може бути на ній намальовано, якщо всі вершини повинні лежати у вузлах сітки, а сторони бути або горизонтальними, або вертикальними, або діагональними (під кутом 45 градусів)? Шириною сітки назвемо кількість вузлів у кожному її ряду, а висотою – кількість вузлів у кожному її стовпчику. Багатокутники, які потрібно знайти, повинні мати такі властивості:
|
- їх вершини повинні лежати у вузлах решітки; |
|
- всі сторони горизонтальні, вертикальні або діагональні (45 градусів); |
|
- багатокутник опуклий. |
Два багатокутники вважаються різними, якщо їх сторони не співпадають, тобто два однакових за формою багатокутника, що знаходяться у різних позиціях, слід вважати за два. Однак додавання вершини у середину ребра не змінює його форми і не утворює новий (для підрахунку) багатокутник.За заданими шириною і висотою поля знайдіть кількість багатокутників.
Формат введення-виведення: Програма Numconv зчитує з клавіатури (стандартного пристрою введення) два натуральні числа a та b (2≤a,b≤100) – ширину та висоту сітки. Програма Numconv виводить на екран (стандартний пристрій виведення) єдине число – кількість можливих багатокутників.
Приклад вхідних та вихідних даних
Введення 1 Виведення 1
3 2 19
Введення 2 Виведення 2
2 2 5