به شما یک $n$ ضلعی محدب دادهایم. به ازای هر نقطه $p$ درون $n$ ضلعی $f(p)$ برابر است با کمترین تعداد از رئوس $n$ ضلعی که اگر آنها را از $n$ ضلعی حذف کنیم، $p$ کاملاً درون چندضلعی نباشد.
شما باید $p$ ای را بیابید که $f(p)$ بیشینه است و $f(p)$ را در خروجی چاپ نمایید.
در سطر اول ورودی عدد $1 \leq n \leq 5 \times 10^4 $ آمده است، در $n$ سطر بعدی مختصات نقاط چندضلعی به ترتیب ساعتگرد آمده است.
در تنها سطر خروجی پاسخ سؤال را چاپ نمایید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 0 0 50 50 60 10 | 1 |
| 5 0 0 0 10 10 20 20 10 25 0 | 2 |
پاسخ
فرض کنید $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)$ محاسبه کرد. میتوانید الگوریتم پیدا کردن اشتراک چند نیمصفحه را از این آدرس بهدست آورید.
پیچیدگی
راهحل سؤال تشکیل شده از $logn$ بار بررسی کردن این که آیا $n$ نیمصفحه با یکدیگر اشتراک دارند یا نه. هر کدام از بررسیها را میتوان در زمان $o(n)$ انجام داد، پس میتوان کل سؤال را در زمان $o(n logn)$ پاسخ داد.