المپدیا

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

ابزار کاربر

ابزار سایت


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

خطوط نامتقاطع

مختصات $n$ نقطه‌ی $A_1$، $A_2$، … و $A_n$ و $n$‌ نقطه‌ی $B_1$، $B_2$، … و $B_n$ داده شده‌اند. $n$‌پاره‌خط رسم کنید به طوری که هر پاره‌خط یک نقطه از $A_i$ ها را به نقطه‌ای از $B_i$ ها وصل کند و این پاره‌خط‌ها یک‌دیگر را قطع نکند.

برنامه‌ی شما باید این مکان را داشته باشد که یا ورودی را از فایل بخواند و یا مختصات نقاط ورودی را به صورت تصادفی ایجاد کند. در سطر اول فایل ورودی عدد $n$(که از ۲۰۰ بیش‌تر نیست)، در $n$ سطر بعد مختصات $A_i$ ها و در $n$ سطر آخر نیز مختصات $B_i$ها نوشته شده است. خروجی را به صورت گرافیکی نشان دهید.

آیا این مسئله به ازای کلیه‌ی اعداد ورودی جواب دارد؟ اگر جوابتان آری است به صورت کتبی آن را ثابت کنید و در صورتی که جوابتان خیر است مثال نقض بیاورید.


ابزار صفحه