المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۳:سوال ۸

سوال ۸

یک چند ضلعی ساده (چند ضلعی که اضلاعش هم‌دیگر را قطع نکنند) با مختصات راس‌های آن داده شده است. همچنین مختصات دو نقطه‌ی $P_1$ و $P_2$ داخل چند ضلعی و عدد حقیقی و مثبت $R$ داده شده‌اند، به‌طوری که دایره‌های به مرکز $P_1$ یا $P_2$ و به شعاع $R$ کاملا داخل چند ضلعی واقع می‌شوند.

برنامه‌ای بنویسید که داده‌های فوق را از ورودی دریافت نماید و :

  1. درستی داده‌ها را با توجه به شرایط فوق (ساده بودن چند ضلعی و قرار گرفتن دایره‌ها درون چند ضلعی) چک کند.
  2. در صورت امکان مسیری از $P_1$ به $P_2$ پیدا کند که در صورتی‌که مرکز دایره به شعاع $R$ روی آن مسیر حرکت کند، بدون این‌که اضلاع چند ضلعی را قط کند از $P_1$ به $P_2$ برسد.

ابزار صفحه