Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۱۲:سوال ۲

دوایر مسلط

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

برای این کار ابتدا مجموعه‌ی تهی S را در نظر می‌گیریم. سپس یکی از نقاط را به‌ دل‌خواه انتخاب می‌کنیم و در مجموعه‌ی S قرار می‌دهیم. در مرحله‌ی اول نقطه‌ای را به مجموعه‌ی S اضافه می‌کنیم که بیش‌ترین فاصله را با نقطه‌ی درون S دارد؛ این فاصله را a1 می‌نامیم. به همین ترتیب در مرحله‌ی iام نقطه‌ای را به مجموعه‌ی S اضافه می‌کنیم که بیش‌ترین فاصله را از مجموعه‌ی S دارد (فاصله‌ی یک نقطه‌ی دل‌خواهِ A از مجموعه نقاط S را فاصله‌ی A تا نزدیک‌ترین نقطه‌ی S به A تعریف می‌کنیم). این بیش‌ترین فاصله را ai می نامیم. بعد از انجام k1 مرحله، حال مجموعه‌ی S شامل k نقطه است و فاصله های a1، a2، …، و ak1 تعیین شده اند. فرض کنید مرحله‌ی kام را نیز انجام دهیم ولی با این تفاوت که در این مرحله نقطه ی به دست آمده را به S اضافه نمی‌کنیم، و فقط فاصله‌ی ak را یادداشت می‌کنیم.

الف) ثابت کنید اگر k دایره به مراکز نقاط درون S و به شعاع ak در صفحه رسم کنیم، این دایره‌ها تمام n نقطه را در بر می‌گیرند.

ب) ثابت کنید به ازای هر عدد r، اگر k دایره‌ی دل‌خواه به شعاع r وجود داشته باشند که تمام n نقطه را در بر گیرند، آن‌گاه خواهیم داشت: ak2r.


ابزار صفحه