DA-F94-CA4-1
Time Limit: 1 Second Memory Limit: 65536 KB
لوك خوش شانس به تازگي به شهر تهران آمده و قصد تحصيل در دانشگاه تهران را دارد. او نميخواهد در اولين حضورش در دانشگاه تهران دير به كلاس ها برسد لذا قصد دارد كمترين "فاصله زماني" از خانه اش تا دانشگاه را بيابد. سرعت متوسط پياده روي لوك ۱۰۰ متر بر دقیقه است و سرعت متوسط مترو ها در تهران ۵۰۰ متر بر دقیقه ميباشد. از آنجا که لوك بسيار خوش شانس است هر وقت وارد ايستگاه مترو شود بلافاصله وارد مترو ميشود. لوك به تعداد نامحدود ميتواند سوار مترو شود و از مترو خارج شود و خط عوض كند (ممكن است لوك مجبور باشد براي عوض كردن خط مترو زماني را پياده حركت كند تا به ايستگاهي در خط ديگري برسد) و در ضمن فرض ميكنيم همه خط هاي مترو دو طرفه باشند. شما بايد كمترين زمان رسيدن لوك خوش شانس به دانشگاه را بيابيدInput
ورودي شامل بلوك هايي است كه هر كدام به شرح زير ميباشد: خط اول هر بلوك شامل پنج عدد است كه اولي n تعداد خط هاي مترو در تهران و چهار عدد بعدي به ترتيب مختصات x و y خانه لوك و دانشگاه تهران ميباشند (پنج عدد -١ به معناي پايان ورودي است) در n خط بعدي در هر خط مختصات x و y ايستگاه هاي يكي از خطوط مترو تهران آمده و هر خط با -1 و -1 به عنوان x و y پايان ميپذيرد در هر خط مترو، مترو بين دو ايستگاه پشت هم فاصله اقليدسي (خط راست) را طي ميكندOutput
خروجي به ازای هر بلوک ورودی كمترين تعداد دقيقه براي رسيدن لوك از خانه به دانشگاه ميباشد (جواب را به نزديك ترين دقيقه گرد كنيد)Sample Input
2 0 0 1000 1000 0 200 500 200 700 200 -1 -1 200 600 500 600 1000 600 -1 -1 2 0 0 10000 10000 0 2000 5000 2000 7000 2000 -1 -1 2000 6000 5000 6000 10000 6000 -1 -1 -1 -1 -1 -1 -1
Sample Output
12 119Submit