در این قسمت به الگوریتم پوسته محدب نقاط و جاروب صفحه می‌پردازیم. برای مسایل ساده‌ی هندسی مثل تقاطع، مساحت و … به کدهای آماده مراجعه کنید که در آنها برنامه‌ها نظرات کافی دارند.

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

با کمک تابع ساعتگرد/پادساعتگرد می‌توان تشخیص داد که یک نقطه درون یا بیرون چندضلعی محدب است. اگر چندضلعی محدب با ترتیب پادساعتگرد داده شده باشد و $pp_ip_{i+1}$ به ازای همه‌ی اضلاع پادساعتگرد باشد (نقطه‌ی داده شده سمت چپ یال باشد)، اگر نقطه $p$ درون چندضلعی باشد. در غیر این صورت $p$ خارج از چندضلعی است.

این تابع را برای محاسبه‌ی پوسته‌ی محدب نیاز داریم.

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

در این الگوریتم سمت چپ‌ترین و پایین‌ترین نقطه را پیدا می‌کنیم (این نقطه حتماً عضو پوسته محدب است). سپس شروع می‌کنیم به ازای هر نقطه آن را اضافه می‌کنیم و بررسی می‌کنیم که آیا زاویه‌ی ساخته شده پادساعتگرد است یا خیر، اگر نبود رأسهای قبل را حذف می‌کنیم تا پادساعتگرد شود. با ادامه این کار به نقطه شروع برمی‌گردیم و پوسته محدب به دست می‌آید.

زمان اجرای این الگوریتم $O(nh)$ است که $n$ تعداد نقاط داده شده و $h$ اندازه‌ی جواب است که می‌تواند حداکثر $n$ باشد.

مطالب بیشتر در مورد الگوریتم کادوپیچی

در این الگوریتم یک نقطه‌ی گوشه‌ای را که می‌دانیم جزو رأسهای پوسته‌ی محدب است، پیدا می‌کنیم. برای این کار مثلاً نقطه با کمترین طول و بعد کمترین عرض را انتخاب می‌کنیم. سایر نقاط را بر اساس زاویه‌شان با این نقطه مرتب می‌کنیم (نیازی به محاسبه‌ی زاویه‌ها نیست و می‌توان از تابع ساعتگرد و پادساعتگرد استفاده کرد). سپس به همین ترتیب نقاط را اضافه می‌کنیم و بررسی می‌کنیم که آیا آخرین گوشه ساخته شده پادساعتگرد است یا خیر، اگر نبود نقطه‌های قبلی را حذف می‌کنیم تا جایی که پادساعتگرد شود. پایان الگوریتم جایی است که به نقطه‌ی شروع برگردیم.

زمان اجرای این الگوریتم $O(n\log n)$ است که به دلیل مرتب‌سازی است.

مطالب بیشتر در مورد الگوریتم پیمایش گراهام

در این الگوریتم ابتدا نقاط به ترتیب $x$ و سپس $y$ مرتب می‌شوند، سپس اولین نقطه (سمت‌چپ‌ترین و بعد پایین‌ترین نقطه) را در نظر گرفته و نقاط را به ترتیب مرتب شده می‌بینیم و اگر گوشه ساخته شده پادساعتگرد نبود نقاط قبل را حذف می‌کنیم. (مشابه الگوریتم‌های قبل). با این کار پوسته‌ی پایینی نقاط ساخته می‌شوند. بار دیگر این کار را به ازای نقطه‌ی آخر در مرتب‌سازی و به ترتیب عکس این لیست انجام می‌دهیم تا پوسته بالایی ساخته شود. این دو پوسته را به هم می‌چسبانیم تا پوسته‌ی محدب به دست بیاید.

زمان اجرای این الگوریتم $O(n\log n)$ است اما از الگوریتم قبل ساده‌تر به نظر می‌رسد.

مطالب بیشتر در مورد الگوریتم پوسته بالایی-پوسته پایینی

الگوریتم‌های جاروب صفحه به این صورت هستند که ابتدا اگر نقاط مرتب نیستند، آنها را بر حسب یکی از مختصاتشان مرتب می‌کنیم. سپس بر اساس آن مختص، جلو می‌رویم و هر بار جواب را به روز می‌کنیم.

برای مثال مسأله‌ی مساحت درون مجموعه‌ای از مستطیلها را با استفاده از جاروب صفحه و اجتماع بازه‌های ساخته شده در هر قسمت محاسبه کرد.
مثال دیگر استفاده از جاروب صفحه، پیدا کردن تقاطع پاره‌خط‌ها است که با استفاده از جاروب صفحه و نگه‌داری ترتیب خطوط می‌توان آن را محاسبه کرد.
مطالب بیشتر در مورد جاروب صفحه

۱- $N\ (1\leq N \leq 100000)$ نقطه داده شده‌اند، خطی را پیدا کنید که از مبدأ بگذرد و بیشترین تعداد تقاطع با این نقاط را داشته باشد.

جواب: شیب نقاط را حساب کنید و مثلاً با داده‌ساختار دیکشنری map آنها را به تعدادشان مربوط کنید و شیب با بیشترین تکرار را بیابید. برای اینکه بتوانید نقطه متناظر را به دست بیاورید می‌توانید داده‌ساختار جدیدی تعریف کنید و تابع مقایسه بر اساس فقط تعداد بنویسید یا از داده‌ساختار زوج مرتب به همراه دیکشنری استفاده کنید که اولین بعد آن تعداد نقاط و دومین بعد آن شیب خط باشد. با داشتن شیب و یک نقطه (مبدأ) می‌توانید خط را به دست بیاورید.

۲- $N\ (1\leq N \leq 2000)$ نقطه داده شده است، تعداد متوازی الاضلاع‌های ساخته شده با این نقطه را پیدا کنید.

جواب: راهنمایی: به ازای هر سه نقطه بررسی کنید که نقطه‌ی سوم برای تشکیل یک متوازی الاضلاع وجود دارد یا خیر.

۳- $N\ (1\leq N \leq 250)$ تیر چوبی در صفحه داده شده‌اند، بیشترین تعداد تیرهایی که می‌توان در یک حصار محدب قرار داد چندتا است؟

جواب: تعداد رأسهای پوسته محدب. می‌توانید آن را با اجرای هر کدام از الگوریتم‌های گفته شده به دست بیاورید.

۴- $N\ (1\leq N \leq 50000)$ گاو حسن در طول یک حصار یک بعدی در حال چریدن هستند. گاو $i$-ام در مکان $x(i)$ ایستاده است و ارتفاع $h(i)\ 1\leq x(i), h(i) \leq 1000000000)$ دارد. یک گاو احساس شلوغی می‌کند اگر گاو دیگری با قد حداقل دو برابر ارتفاع اون در فاصله کمتر از $D$ در سمت چپ او باشد و گاو دیگری با همین مشخصات در سمت راست او باشد. $(1\leq D \leq 1000000000)$. تعداد گاوهایی که احساس شلوغی می‌کنند چندتا است؟

جواب: راهنمایی: استفاده از جاروب صفحه یک بار از راست به چپ و یک بار از چپ به راست و نگه داشتن مقدار بیشینه در بازه با فاصله حداکثر $D$ از مکان گاو (محل خط جاروب).

۵-گاوها در مکان‌های مستطیل شکل در حال چریدن هستند. این مکان‌های مستطیلی داده شده‌اند. در زمان $O(N\log N)$ مساحت کل این چراگاه‌ها را پیدا کنید. مستطیل‌ها می‌توانند اشتراک داشته باشند.

جواب: به درخت پاره‌خط‌ها نگاه کنید.

۶- $N\ (1\leq N \leq 100000)$ نقطه در دومین قسمت از چهار قسمت دستگاه مختصات و دو زاویه داده شده‌اند. یک خر با شروع از مبدأ می‌تواند به یک نقطه بین دو شعاع رسم شده از مبدأ با زاویه‌های داده شده نسبت به محور $x$ برود. سپس این عمل را با نقطه جدید انجام می‌دهد. بیشترین تعداد نقاطی که این خر می‌تواند ببیند چقدر است؟

جواب: راهنمایی: گراف متناظر آن را بسازید که رأسها متناظر نقاط هستند و یالها نشان‌دهنده‌ی مجاز بودن حرکت. سپس با استفاده از طولانی‌ترین مسیر در گراف جهت‌دار بدون دور مسأله را حل کنید.

منبع سوالات