المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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

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

ورودی

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

$N1 \\ A11 \quad A12 \quad B11 \quad B12 \\ A21 \quad A22 \quad B21 \quad B22 \\ A31 \quad A32 \quad B31 \quad B32 \\ .... \\ .... \\ AN11 \quad AN12 \quad BN11 \quad BN12 \\ \quad \\ \quad \\ N2 \\ A11 \quad A12 \quad B11 \quad B12 \\ A21 \quad A22 \quad B21 \quad B22 \\ A31 \quad A32 \quad B31 \quad B32 \\ .... \\ .... \\ AN21 \quad AN22 \quad BN21 \quad BN22$

خروجی

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

$Solution \quad For \quad The \quad Data Set \quad \# \quad 1 \\ x \quad Lamps \quad is \quad needed \quad at \quad least.\quad Their \quad possible \quad locations \quad are: \\ V11 \quad V12 \\ .... \\ .... \\ Vx1 \quad Vx2 \\ \quad \\ Solution \quad For \quad The \quad Data Set \quad \# \quad 2 \\ y \quad Lamps \quad is \quad needed \quad at \quad least.\quad Their \quad possible \quad locations \quad are: \\ V11 \quad V12 \\ ... \\ Vy1 \quad Vy2$


ابزار صفحه