ბაყაყები

დროის ლიმიტი: 7 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: პოლონეთი, ოლიმპიადა 13, ეტაპი 1


ბაყაყები ბაიტლენდს კატასტროფას უქდიან. ისინი აპირებენ გაანადგურონ მთლიანი მოსავალი. ფერმერმა ბაიტაზარმა გადაწყვიტა ბაყაყების წინააღმდეგ გალაშქრება და სპეციფიკური საფრთხობელების გამოყენება, რომელთან იგი კონკრეტულ წერტილებში განალაგებს. თითოეული ბაყაყი გადაადგილებისას ცდილობს თავი მაქსიმალურად შორს დაიჭიროს საფრთხობელებისაგან, ანუ მაქსიმიზირებს მასთან ყველაზე ახლოს მდებარე საფრთხობელასთან დაშორებას.

ბაიტაზარის მინდორი არის მართკუთხედის ფორმის. ბაყაყები კი ხტებიან მისი გვერდების პარალელურად მხოლოდ ერთი ერთეულით. ისინი მოძრაობას იწყებენ რაღაც კონკრეტულ (px, py) წერტილში და მოგზაურობას ამთავრებენ (kx, ky) საბოლოო წერტილში.

ბაიტაზარმა აქვს წინასწარმეტყველება სად გამოჩნდებიან ბაყაყი ყველაზე ხშირად შესაბამისად გადაწყვიტა კონკრეტულ ადგილებში განელაგებინა საფრთხობელები. ახლა კი თხოვნით მოგმართავს რათა გამოთვალო ბაყაყის გადაადგილების განმავლობაში ყველაზე მცირე დაშორება მასსა და საფრთხობელას შორის (ანუ ბაყაყის თითოეული ადგილმდებარეობისათვის რომ შევხედოთ ყველაზე ახლოს მდებარე საფრთხობელასთან მანძილს და ამ მანძილებიდან საბოლოოდ კიდევ ყველაზე მცირე ავარჩიოთ. მარტივად რომ ვთქვათ უნდა იპოვოთ მთელი ამ მოგზაურობის მანძილზე რა მანძილი იქნება მინიმალური რომელზეც ბაყაყი რომელიმე მაინც საფრთხობელას მიუახლოვდება).

დავალება:

 დაწერეთ პროგრამა, რომელიც:

·                     წაიკითხავს სტანდარტულ შემომავალი ინფორმაციიდან: მინდვრის სიგრძესა და სიგანეს, საფრთხობელების განლაგების წერტილებსა და ბაყაყის საწყის და საბოლოო პოზიციას;

·                     გამოთვლის მოგზაურობის განმავლობაში ყველაზე მცირე მანძილს, რომელზედაც რომელიმე მაინც საფრთხობელას ბაყაყი მიუახლოვდება;

·                     სტანდარტულ გამოსატან მოსაცემებში გამოიტანს ამ მინიმალური დაშორების კვადრატს.

 შემოსატანი მონაცემები:

 პირველი ორი ხაზი შეიცავს ორ რიცხვს: Wx-სა და Wy-ს, ანუ მინდვრის სიგანესა და სიგრძეს (შესაბამისად X და Y საკოორდინატო ღერძის პარალელურად მდებარეობენ), რომელთა მნიშვნელობებისთვის სრულდება შემდეგი უტოლობა 2 ≤ Wx, Wy ≤ 1000.

მეორე ხაზი შეიცავს ოთხ რიცხვს: px, py, kx, ky ( გამოყოფილები ერთმანეთისგან არიან ერთი სფეისით). (px, py) არის ბაყაყის საწყისი პოზიცია, ხოლო (kx, ky) საბოლოო ანუ სადაც უნდა მივიდეს. ამასთან 1 ≤ px, kx ≤ Wx და 1 ≤ py, ky ≤ Wy.

მესამე ხაზი შეიცავს ერთ რიცხვს: N-ს, საფრთხობელების რაოდენობას.

მეოთხედან დაწყებული შემდეგი N ხაზი შეიცავს ორ რიცხვს, რომლებიც წარმოადგენენ i-ური საფრთხობელის ადგილსამყოფელის კოორდინატებს. ამასთან: 1 ≤ xi ≤ Wx და 1 ≤ yi ≤ Wy. ასევე, ორი სხვადასხვა საფრთხობელა ერთსადაიმავე პოზიციაზე არასდროს არ იდგმება, ანუ (x, y) წყვილი ყველა საფრთხობელასთვის უნიკალურია და ამასთან იგი არ დაემთხვევა ბაყაყის არც საწყის და არც საბოლოო პოზიციას.

 გამოსატანი მონაცემები:

 პირველი და უკანასკნელი ხაზი უნდა შეიცავდეს ერთ რიცხვს, ბაყაყის მოგზაურობის განმავლობაში ყველაზე ახლოს მდებარე საფრთხობელასთან დაშორების (მანძილის) კვადრატს. იმ შემთხვევაში თუ ბაყაყი ვერ მოახერხებს თავიდან აირიდოს საფრთხობელას კოორდინატზე დახტომა, შესაბამისად პასუხი იქნება 0.




მაგალითები

შესატანი მონაცემები
5 5 1 1 5 5 2 3 3 4 2 დაკოპირება
გამოსატანი მონაცემები
4 დაკოპირება