====== 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}$‎ گرد کنید.‎ ===== محدودیت‌ها ===== * محدودیت زمان: ۲ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |193‎ \\ 3‎ \\ 82‎ \\ 13‎ \\ 100 | 0 | |1000000‎ \\ 3‎ \\ 100‎ \\ 92‎ \\ 77 | 9 | * [[سوال ۴۳|سوال بعد]] * [[سوال ۴۱|سوال قبل]]