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

المپدیا

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

ابزار کاربر

ابزار سایت


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

نور رسانی به گالری

در یک گالری n تابلوی نقاشی موجود است. می‌خواهیم با حداقل تعداد لامپ‌ها به کلیه تابلو‌های نقاشی نور برسانیم. هر تابلوی نقاشی را یک پاره‌خط فرض نمایید که می‌تواند موازی یک‌دیگر باشندولی یک‌دیگر را قطع نمی‌کنند. پاره‌خط‌ها دارای پهنایی نیستند و منظور ما از نور رسانی به این پاره‌خط‌ها این است که تمامی نقاط آن‌ها در معرض تشعشع نور لامپ‌ها قرار گیرد. یک نقطه از یک خط از یک لامپ نور دریافت می‌کند اگر پاره‌خط رسم شده بین آن نقطه و لامپ هیچ یک از n پاره‌خط را قطع نکند.

برنامه‌ای بنویسید تا با دریافت n و مختصات دو سر این n پاره‌خط، حداقل تعداد این لامپ‌ها و مختصات هر یک را در فایل خروجی چاپ نمایید.

ورودی

فایل ورودی با قالب زیر. فرض کنید که مختصات داده شده اعداد صحیح هستند.

N1A11A12B11B12A21A22B21B22A31A32B31B32........AN11AN12BN11BN12N2A11A12B11B12A21A22B21B22A31A32B31B32........AN21AN22BN21BN22

خروجی

فایل خروجی با قالب زیر.

SolutionForTheDataSet#1xLampsisneededatleast.Theirpossiblelocationsare:V11V12........Vx1Vx2SolutionForTheDataSet#2yLampsisneededatleast.Theirpossiblelocationsare:V11V12...Vy1Vy2


ابزار صفحه