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}$ گرد کنید.

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