Օպտիմալացնել շինարարական գործընթացը
Ձեզ աշխատանքի են ընդունել շինարարական ընկերությունում, որպեսզի օպտիմալացնենք ծանր շինանյութերի տեղափոխման գործընթացը շինհրապարակի տարբեր կետերի միջև:
Շինարարական տարածքը ուղղանկյունաձև դաշտ է, որի լայնությունը
w է, իսկ բարձրությունը h։ Կարող ենք այն դիտարկել որպես ուղղանկյուն, որի ստորին ձախ անկյունը (0, 0) կոորդինատն է, իսկ վերին աջ անկյունը (w, h) կոորդինատը։ Մուտքը տեղակայված է շինհրապարակի ներքևի հատվածի կենտրոնում։Շինհրապարակի տարբեր դիրքերում տեղադրված են
n կռունկներ (), և նրանցից յուրաքանչյուրն ունի իր պտտվող стрелայով (jib) հասանելիության շառավիղ ։ Կռունկները կարող են պտտվել 360°-ով, ուստի եթե ծանրոցը գտնվում է որևէ կռունկի հասանելիության շառավղում, նա կարող է տեղափոխել այն։Ձեզ Several վերջնական կետեր (destination points) են տալիս, և անհրաժեշտ է պարզել, թե քանի նվազագույն կռունկ է պահանջվում, որպեսզի մուտքից սկսած նյութերը հնարավոր լինի հասցնել այդ վերջնական կետ:
Մուտք
Մուտքի առաջին տողում տրված են
w և h ամբողջ թվերը (2 ≤ w, h ≤ 200), ընդ որում w-ն զույգ թիվ է։Հաջորդ տողում տրված է
n ամբողջ թիվը (1 ≤ n ≤ 50)՝ ցույց տալով կռունկների քանակը։Հաջորդ
n տողերից յուրաքանչյուրում տրված են 3 ամբողջ թիվ — համապատասխան կռունկի կոորդինատները և դրա հասանելիության շառավիղը (0 ≤ ≤ w), (0 ≤ ≤ h), (0 ≤ ≤ 200):Այնուհետև տրվում է մեկ ամբողջ թիվ
k (1 ≤ k ≤ 30), որը ցույց է տալիս վերջնական կետերի քանակը։Հաջորդ
k տողերից յուրաքանչյուրում նշված են 2 ամբողջ թիվ (0 ≤ ≤ w, 0 ≤ ≤ h), որոնք վերջնական կետի կոորդինատներն են։Ելք
Ծրագիրը պետք է տպի
k տող, որոնցից յուրաքանչյուրում ցույց կտա մինչև տվյալ վերջնական կետ հասնելու համար անհրաժեշտ կռունկների նվազագույն քանակը։ Եթե տվյալ վերջնական կետը հասանելի չէ, ծրագիրը պետք է տպի Impossible:Օրինակներ
Մուտք | Ելք |
4 4
2
2 1 1
2 3 1
5
2 2
3 2
1 2
2 3
3 3 | 1
Impossible
Impossible
2
2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB