Polygon

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

‎ دو نقطه ی ‎$s$‎ و ‎$t$‎ روی صفحه داده شده‌اند. می‌دانیم ‎$s$‎ و ‎$t$‎ داخل ‎$P$‎ یا روی اضلاع آن نیستند. شما باید طول کوتاه‌ترین مسیر خوب از ‎$s$‎ به ‎$t$‎ را بیابید.‎

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

• مشخصات ‎$P$‎ و ‎$q$‎ جفت نقطه‌ی ‎$s_i$‎ و ‎$t_i$‎ را از ورودی بخواند؛
• طول کوتاه‌ترین مسیر خوب بین هر ‎$s_i$‎ و ‎$t_i$‎ را پیدا کند و در خروجی بنویسید.

• در هر سطر اول ورودی، دو عدد صحیح ‎$n$‎ و ‎$q$‎ به ترتیب نوشته شده‌اند.‎
• در هر یک از ‎$n$‎ سطر بعدی، دو عدد ‎$x$‎ و ‎$y$‎ نوشته شده است که مختصات یک راس از ‎$P$‎ را مشخص می کند. رئوس ‎$P$‎ به ترتیب ساعت‌گرد یا پادساعت‌گرد داده شده‌اند.‎
• در سطر ‎$i$‎ام از ‎$q$‎ سطر بعدی، چهار عدد $x_1$، $y_1$، $x_2$ و $y_2$ نوشته شده‌اند که ‎$(x_1, y_1)$‎ مختصات ‎$s_i$‎ و ‎$(x_2, y_2)$‎ مختصات ‎$t_i$‎ است.
• قدرمطلق تمام اعداد ورودی کم‌تر یا مساوی ‎$1000$‎ است و همه مختصه‌ها حداکثر تا ۴‎ رقم اعشار به شما داده می‌شوند.‎
• ‎$1 \leq q \leq 1000$‎

در سطر ‎$i$‎ام از خروجی طول کوتاه‌ترین مسیر خوب بین ‎$s_i$‎ و ‎$t_i$‎ را تا ‎۴‎ رقم اعشار بنویسید. عدد خود را به نزدیک‌ترین ضریب صحیح ‎$10^{-4}$‎ گرد کنید.‎

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

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