المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱

یک خط به نام $L$ و $n$ نقطه داریم به طوری که هیچ کدام از این $n$ نقطه روی خط قرار ندارند. هدف مسئله این است که موقعیت نقاط را نسبت به خط پیدا کنیم.

ورودی و خروجی

ورودی را از $stdin$ بخوانید. در سطر اول دو عدد $n$ و $k$ آمده‌اند. سپس $k$ خط آمده که هر خط یا به شما اطلاعات می‌دهد و یا از شما اطلاعات می‌پرسد. اول هر خط یک عدد $z$ آمده. ($n$ و $k$ هیچ‌کدام از $10^6$ بیش‌تر نیستند.)

اگر $z$ برابر ۰ باشد، سه عدد دیگر هم پس از $z$ می‌آیند، $x$، $y$ و $cross$. بدین صورت به شما اطلاع داده می‌شود که آیا پاره‌خط بین نقاط $x$ و $y$، خط $L$ را قطع می‌کند یا نه. اگر قطع بکند، $cross$ برابر ۱ می‌شود و در غیر این صورت ۰ است.

اگر در خط $i$ ام، $z$ برابر ۱ باشد، دو عدد دیگر $x$ و $y$ هم می‌آیند. در این صورت، شما باید بر اساس اطلاعاتی که تا خط $i-1$ ام داریم، یکی از سه پیام زیر را در یک خط به $stdout$ بنویسید:

$(a)$ اگر پاره‌خط بین نقاط $x$ و $y$، حتما خط $L$ را قطع می‌کند، YES

$(b)$ اگر پاره‌خط بین نقاط $x$ و $y$، یقینا خط $L$ را قطع نمی‌کند، NO

$(c)$ اگر با اطلاعات فعلی نمی‌شود به طور قطعی وضعیت را مشخص کرد، N/A

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
5 9
1 1 4
0 1 2 0
0 3 4 0
1 3 4
0 2 3 1
1 1 4
1 2 5
0 3 5 0
1 2 5
N/A
NO
YES
N/A
YES

ابزار صفحه