Условие
G. ПЪТИЩА
---
Разглеждаме точки с целочислени координати (x,y) в равнината. Някои от точките са свързани с хоризонтална или вертикална отсечка до някои от четирите им най-близки точки измежду дадените, намиращи се отгоре, отдолу, отляво или отдясно. Път, свързващ две точки наричаме последователност от описаните отсечки, чрез които от едната точка може да отидем до другата. Два пътя са различни, ако съответните им последователности от отсечки са различни. В един път може да има повторения на едни и същи отсечки. Дължина на пътя е броят на отсечките в последователността, определяща пътя. Напишете програма, която намира колко различни пътя с дадена дължина свързват две дадени точки.
Вход. На първия ред на стандартния вход е зададен броят на тестовете. Данните за всеки тест започват с ред, съдържащ броя k на отсечките. Следват k реда, всеки описващ една отсечка: две двойки координати, задаващи двете крайни точка на отсечката. Следва ред, съдържащ дължината L на търсените пътища и броя Q на въпросите към програмата. Всеки въпрос е записан на отделен ред и се състои от координатите на две точки. Числата във входа са разделени с интервали. Дадените отсечки са различни. Различни са и двете крайни точки на всяка отсечка.
Изход: Програмата трябва да изведе за всеки тест на отделен ред на стандартния изход по едно цяло неотрицателно число, съответстващо на търсения брой (пресметнат по модул 100000007) пътища с дължина L по реда на въпросите.
Ограничения: 1 < k < 190; 0 < L < 100; 0 < Q < 7. Координатите на точките във входа са цели положителни числа, по-малки от 15.
Примерен вход:
2
7
1 3 2 3
2 3 3 3
3 3 4 3
1 2 2 2
2 2 2 1
2 1 1 1
1 1 1 2
4 2
1 3 3 3
2 2 1 1
3
1 1 1 2
1 2 1 3
1 3 1 4
5 2
1 1 1 3
1 1 1 4
Примерен изход:
3
8
0
3
« Предходна страница
Решение
Въпрос