مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

این صفحه فقط خواندنی است. شما می‌توانید متن صفحه را مشاهده کنید، اما نمی‌توانید آن را تغییر دهید. اگر فکر می‌کنید که مشکلی رخ داده است، مدیر ویکی را در جریان بگذارید.
====== هندسه محاسباتی ======
در این قسمت به الگوریتم پوسته محدب نقاط و جاروب صفحه می‌پردازیم. برای مسایل ساده‌ی هندسی مثل تقاطع، مساحت و ... به [[آماده‌سازی:کدهای_آماده|کدهای آماده]] مراجعه کنید که در آنها برنامه‌ها نظرات کافی دارند.
===== ساعتگرد و پادساعتگرد =====
برای تشخیص ساعتگرد بودن سه نقطه می‌توانیم از ضرب خارجی استفاده کنیم که معادل محاسبه‌ی دترمینان یک ماتریس است که وقتی آن را باز کنیم، مجموعه‌ای از عملیات جمع و تفریق و ضرب است. (رجوع کنید به [[آماده‌سازی:کدهای_آماده|کدهای آماده]])
==== تشخیص نقطه درون و بیرون از چندضلعی محدب ====
با کمک تابع ساعتگرد/پادساعتگرد می‌توان تشخیص داد که یک نقطه درون یا بیرون چندضلعی محدب است. اگر چندضلعی محدب با ترتیب پادساعتگرد داده شده باشد و $pp_ip_{i+1}$ به ازای همه‌ی اضلاع پادساعتگرد باشد (نقطه‌ی داده شده سمت چپ یال باشد)، اگر نقطه $p$ درون چندضلعی باشد. در غیر این صورت $p$ خارج از چندضلعی است.

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

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

[[http://en.wikipedia.org/wiki/Gift_wrapping_algorithm|مطالب بیشتر در مورد الگوریتم کادوپیچی]]
==== الگوریتم پیمایش گراهام ====
در این الگوریتم یک نقطه‌ی گوشه‌ای را که می‌دانیم جزو رأسهای پوسته‌ی محدب است، پیدا می‌کنیم. برای این کار مثلاً نقطه با کمترین طول و بعد کمترین عرض را انتخاب می‌کنیم. سایر نقاط را بر اساس زاویه‌شان با این نقطه مرتب می‌کنیم (نیازی به محاسبه‌ی زاویه‌ها نیست و می‌توان از تابع ساعتگرد و پادساعتگرد استفاده کرد). سپس به همین ترتیب نقاط را اضافه می‌کنیم و بررسی می‌کنیم که آیا آخرین گوشه ساخته شده پادساعتگرد است یا خیر، اگر نبود نقطه‌های قبلی را حذف می‌کنیم تا جایی که پادساعتگرد شود. پایان الگوریتم جایی است که به نقطه‌ی شروع برگردیم.

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

[[http://fa.wikipedia.org/wiki/%D9%BE%DB%8C%D9%85%D8%A7%DB%8C%D8%B4_%DA%AF%D8%B1%D8%A7%D9%87%D8%A7%D9%85|مطالب بیشتر در مورد الگوریتم پیمایش گراهام]]
==== الگوریتم پوسته‌ی بالایی-پوسته‌ی پایینی ====
در این الگوریتم ابتدا نقاط به ترتیب $x$ و سپس $y$ مرتب می‌شوند، سپس اولین نقطه (سمت‌چپ‌ترین و بعد پایین‌ترین نقطه) را در نظر گرفته و نقاط را به ترتیب مرتب شده می‌بینیم و اگر گوشه ساخته شده پادساعتگرد نبود نقاط قبل را حذف می‌کنیم. (مشابه الگوریتم‌های قبل). با این کار پوسته‌ی پایینی نقاط ساخته می‌شوند. بار دیگر این کار را به ازای نقطه‌ی آخر در مرتب‌سازی و به ترتیب عکس این لیست انجام می‌دهیم تا پوسته بالایی ساخته شود. این دو پوسته را به هم می‌چسبانیم تا پوسته‌ی محدب به دست بیاید.

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

[[http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain|مطالب بیشتر در مورد الگوریتم پوسته بالایی-پوسته پایینی]]
===== جاروب صفحه =====
الگوریتم‌های جاروب صفحه به این صورت هستند که ابتدا اگر نقاط مرتب نیستند، آنها را بر حسب یکی از مختصاتشان مرتب می‌کنیم. سپس بر اساس آن مختص، جلو می‌رویم و هر بار جواب را به روز می‌کنیم.

برای مثال مسأله‌ی مساحت درون مجموعه‌ای از مستطیلها را با استفاده از جاروب صفحه و اجتماع بازه‌های ساخته شده در هر قسمت محاسبه کرد.\\
مثال دیگر استفاده از جاروب صفحه، پیدا کردن تقاطع پاره‌خط‌ها است که با استفاده از جاروب صفحه و نگه‌داری ترتیب خطوط می‌توان آن را محاسبه کرد.\\
[[http://help.topcoder.com/data-science/competing-in-algorithm-challenges/algorithm-tutorials/line-sweep-algorithms/|مطالب بیشتر در مورد جاروب صفحه]]
===== مسایل نمونه =====
۱- $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$ برود. سپس این عمل را با نقطه جدید انجام می‌دهد. بیشترین تعداد نقاطی که این خر می‌تواند ببیند چقدر است؟

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

[[http://activities.tjhsst.edu/sct/lectures/1314/intro_comp_geo_12_06_13.pdf|منبع سوالات]]
مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

ابزار کاربر

ابزار سایت

ابزار صفحه
