Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۴۲

Polygon

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

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

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

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

ورودی

  • در هر سطر اول ورودی، دو عدد صحیح ‎n‎ و ‎q‎ به ترتیب نوشته شده‌اند.‎
  • در هر یک از ‎n‎ سطر بعدی، دو عدد ‎x‎ و ‎y‎ نوشته شده است که مختصات یک راس از ‎P‎ را مشخص می کند. رئوس ‎P‎ به ترتیب ساعت‌گرد یا پادساعت‌گرد داده شده‌اند.‎
  • در سطر ‎i‎ام از ‎q‎ سطر بعدی، چهار عدد x1، y1، x2 و y2 نوشته شده‌اند که ‎(x1,y1)‎ مختصات ‎si‎ و ‎(x2,y2)‎ مختصات ‎ti‎ است.
  • قدرمطلق تمام اعداد ورودی کم‌تر یا مساوی ‎1000‎ است و همه مختصه‌ها حداکثر تا ۴‎ رقم اعشار به شما داده می‌شوند.‎
  • 1q1000

خروجی

در سطر ‎i‎ام از خروجی طول کوتاه‌ترین مسیر خوب بین ‎si‎ و ‎ti‎ را تا ‎۴‎ رقم اعشار بنویسید. عدد خود را به نزدیک‌ترین ضریب صحیح ‎104‎ گرد کنید.‎

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
193‎
3‎
82‎
13‎
100
0
1000000‎
3‎
100‎
92‎
77
9

ابزار صفحه