المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۶:سوال ۱۲

Polygon

$n$ ضلعی ساده‌ی $P$ روی صفحه داده شده است. یک مسیر (خم یا خط شکسته) ﺑﯿﻦ ﺩﻭ ﻧﻘﻄﻪﯼ ﺩﻝﺧﻮﺍﻩ ﺭﻭﯼ ﺻﻔﺤﻪ ﺭﺍ«ﺧﻮﺏ» ﻣﯽﻧﺎﻣﯿﻢ ﺍﮔﺮ ﺑﺎ $P$ اشتراک داشته باشد (حتی در یک نقطه و با یکی از اضلاع). مثلا در شکل روبه‌رو مسیرهای $AB$ و $CD$ مسیرهایی خوب هستند.

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

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

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

ورودی

در سطر اول ورودی، دو عدد صحیح $n$ و $q$ به ترتیب نوشته شده‌اند.($1\leq n,q \leq 1000$)

در هر یک از $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$ است.

قدر مطلق تمام اعداد ورودی کم‌تر یا مساوی ۱۰۰۰ است و همه‌ی مختصه‌ها حداکثر تا ۴ رقم اعشار به شما داده می‌شوند.

خروجی

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

محدودیت‌ها

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

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
3 1
0 0
1 0
0 1
1 1 1 -1
2.0000

ابزار صفحه