Rock

سهیل امپراکاش شارما بهترین صخره نورد دنیا تصمیم گرفته که به یکی از زیباترین صخره‌های دنیا به اسم اس پنتاس ‎ صعود کند. در بعضی از نقاط صخره برآمدگی‌هایی وجود دارد که می‌توانند تکیه‌گاهی برای حداکثر یکی از دست‌ها و یا پاهای سهیل باشند. برای راحتی کار صخره را بصورت صفحه‌ی مختصات و برآمدگی های صخره را بصورت نقاط صفحه درنظر می‌گیریم. همچنین سهیل را در این صفحه بصورت چهار پاره‌خط به طول ‎$h$ (طول دست‌ها و پاهایش برابر است!)‎ در نظر میگیریم که همگی در یک نقطه ‎(کمر)‎ به هم متصلند و هر یک می توانند خم یا جمع شوند. در ابتدا هر یک از دست‌ها و پاهای سهیل بر روی یکی از نقاط قرار دارد.

در هر حرکت سهیل می‌تواند دقیقا یکی از دست‌ها و یا پاهایش را بر روی یکی از نقاط دیگر قرار دهد بشرطی که دست یا پایش به آن نقطه برسد. توجه کنید که در هر لحظه حداقل سه نقطه از بدن سهیل باید به نقاط صخره وصل باشد. هم‌چنین بعلت مهارت زیادی که سهیل در صخره نوردی دارد می تواند پاهایش را بالاتر از دستانش قرار دهد.

به‌عبارتی دیگر در صورتی سهیل می‌تواند بر روی چهار نقطه باشد که فاصله‌ی کمرش از دو نقطه‌ای که دستانش بر روی آن قرار دارند و نقاطی که پاهایش بر روی آن قرار دارند حداکثر ‎$h$‎ باشد. حرکت از یک حالت به حالت دیگر وقتی ممکن است که این دو حالت سه نقطه مشترک داشته سهیل به‌تواند در هر ‎۲‎ حالت قرار گیرد.

برنامه‌ای بنویسید که

• مختصات نقاط صخره، طول دست‌ها و پاها، موقعیت اولیه و نهایی سهیل را از ورودی بخواند.
• کمترین تعداد حرکت برای رسیدن سهیل از وضعیت اولیه به وضعیت نهایی را بدست بیاورد و آن را در خروجی چاپ کند.
• فرض کنید همیشه امکان رسیدن به وضعیت نهایی وجود دارد.

• در اولین خط ورودی تعداد نقاط ‎($n$)‎ و طول دست‌ها و پاهای سهیل ‎($h$)‎ آمده است.
• در ‎$n$‎ خط بعدی مختصات نقاط شماره ‎$1$‎ تا ‎$n$‎ به‌ترتیب آمده است.
• در خط بعدی چهار عدد صحیح آمده که شماره‌ی نقاطی است که سهیل در ابتدا بر روی آن‌ها قرار دارد.
• در آخرین خط شماره نقاط وضعیت نهایی که سهیل باید به آن برسد آمده است.
• تعداد نقاط حداکثر برابر ‎۴۰‎ است.
• مختصات نقاط صحیح و بین ‎$(0,0)$‎ و ‎$(1000,1000)$‎ قرار دارد.
• طول دستها و پاهای سهیل صحیح و بین ‎$1$‎ تا ‎$100$‎ است.

در تنها سطر خروجی طول کوتاه‌ترین مسیر ‎(حرکات)‎ برای رسیدن از وضعیت اولیه به وضعیت نهایی را بنویسید.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل

‎‎