====== Towers ======

به شما یک ‎$n$‎ ضلعی محدب داده‌ایم. به ازای هر نقطه ‎$p$‎ درون ‎$n$‎ ضلعی ‎$f(p)$‎ برابر است با کم‌ترین تعداد از رئوس ‎$n$‎ ضلعی که اگر آن‌ها را از ‎$n$‎ ضلعی حذف کنیم، ‎$p$‎  کاملاً درون چندضلعی  نباشد‎.‎

شما باید ‎$p$‎ ای را بیابید که ‎$f(p)$‎ بیشینه است و ‎$f(p)$‎ را در خروجی چاپ نمایید‎.‎
‎===== ورودی =====

در سطر اول ورودی عدد ‎$1 \leq n \leq 5 \times 10^4 $‎ آمده است، در ‎$n$‎ سطر بعدی مختصات نقاط چندضلعی به ترتیب ساعت‌گرد آمده است.
===== خروجي =====

در تنها سطر خروجی پاسخ سؤال را چاپ نمایید‎.‎
‎
===== محدودیت‌ها =====


  * محدودیت زمان: ۴ ثانیه
  * محدودیت حافظه: ۲۵۶ مگابایت
===== ورودي و خروجي نمونه =====

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|3 \\ 0 0 \\ 50 50‎ \\ ‎60 10‎| 1‎|
|5‎ \\ 0 0 \\ 0 10‎‎ \\ 10 20 \\ 20 10‎ \\ 25 0‎|2|
</WRAP>

<پاسخ>
فرض کنید ‎$max_x^x \in Af(x) = k$‎ باشد و ‎$A$‎ مساحت چندضلعی باشد. همچنین فرض کنید که ‎$v(i,t)$‎ برابر با برداری باشد که از رأس ‎$i$‎ام شروع شده و به ‎$t-1$‎امین رأس بعدی خود (به صورت ساعت گرد) می‌رود و ‎$q(i,t)$‎ برابر با نیم‌صفحه‌ای باشد که سمت راست بردار ‎$v(i,t)$‎ قرار دارد.

چون به ازای هر نقطه ‎$k$‎ رأس وجود دارند که با حذف آن‌ها خارج از چند ضلعی قرار می گیرد ،  ‎$\cap_i=1^{n}q(i,k) = \varnothing$‎ و به صورت کلی ‎$\cap_{i=1}^nq(i,k") = \varnothing$‎ به ازای تمام ‎$k \leq k‎" ‎\leq n-2$‎ برقرار است. ‎
‎
همچنین چون حد اقل یک نقطه وجود دارد که ‎$f$‎ آن برابر با ‎$k$‎ باشد ، گزاره زیر به ازای 
تمام ‎$k' < k$‎ ها برقرار است
‎

$\cap_{i=1}^nq(i,k') \neq \varnothing$

‎
پس اگر بتوانیم اشتراک تعدادی نیم‌صفحه را پیدا کنیم ، بااستفاده از الگوریتم ‎binary search‎ می‌توانیم پاسخ سوال (که برابر است با کم‌ترین ‎$k"$‎ ای که شرط اول در آن صدق می کند) را به دست آوریم‎.‎

اشتراک ‎$n$‎ نیم‌صفحه را می‌توان با استفاده از برنامه‌نویسی خطی در زمان ‎$o(n)$‎ محاسبه کرد‎.‎ می‌توانید الگوریتم پیدا کردن اشتراک چند نیم‌صفحه را از این [[http://mpi-inf.mpg.de/kavitha/lecture3.ps|آدرس]]  به‌دست آورید.


**پيچيدگي**


راه‌حل سؤال تشکیل شده از ‎$logn$‎ بار بررسی کردن این که آیا ‎$n$‎ نیم‌صفحه با یکدیگر اشتراک دارند یا نه. هر کدام از بررسی‌ها را می‌توان در زمان ‎$o(n)$‎ انجام داد، پس می توان کل سؤال را در زمان ‎$o(n logn)$‎ پاسخ داد.
</پاسخ>

  * [[سوال ۵۹|سوال بعد]]
  * [[سوال ۵۷|سوال قبل]]