صورت سوال رو خوندید و به اندازه کافی به سوال فکر کردید؟ اگه آره و می‌خواید حالا ایده‌های حل رو ببینید ادامهٔ مطلب رو بخونید:
- فرض کنیم قراره فقط یه دونه چند ضلعی با ضلع‌های داده شده بسازیم. اگه بتونیم این مسئله رو در O(n) حل کنیم بلافاصله یه راه حل O(n^3) با استفاده از dp داریم. بیاید این مسئله رو حل کنیم. ظاهرا یک چند ضلعی منعطف (یعنی می‌شه مثل این سوال زاویه‌هاش رو عوض کرد) وقتی مساحت بیشینه رو داره که همهٔ رئوسش روی یک دایره باشن. اینجا دو تا اثبات برای این قضیه اومده که اولیش بر پایهٔ اینه که با محیط ثابت دایرست که مساحت بیشینه رو داره و دومی هم بر پایهٔ درست بودن این قضیه برای چهارضلعی (بر اساس Bretschneider's formula) اون رو برای n-ضلعی‌ها اثبات می‌کنه. این رو هم اثبات می‌کنه به سادگی که ترتیب ضلع‌ها اهمیتی نداره چون می‌شه هر دو یال مجاوری رو جابجا کرد. بنابراین می‌تونیم روی شعاع دایره باینری سرچ بزنیم و ببینیم می‌تونیم یال‌ها رو روی دایره بچینیم به طوری که خودش رو قطع نکنه؟ اینجا یه سری ظرافت داره البته! باید دو حالت اینکه مرکز دایرهٔ محیطی داخل چند ضلعی بیفته یا خارجش رو جداگونه در نظر گرفت. بهترین راه برای بررسی این امکان هم احتمالا پرداختن به زاویه‌هاست که اینجا قشنگ توضیح داده.
- هنوز تموم نشده! الان یه راه O(n^3 log R) داریم که خوب نیست و تایم می‌شه. اینجا یه فکتی میاد وسط که نمی‌دونم چرا درسته.. اینکه اگه جواب این نباشه که همه رو بکنیم یه چند ضلعی اون وقت بلند ترین یال قطعا استفاده نمی‌شه. بنابراین هر بار جواب رو حساب می‌کنیم برای یک چند ضلعی ساختن، بزرگترین رو می‌اندازیم دور و بازگشتی برای باقی مونده‌ها حل می‌کنیم و بیشینه می‌گیریم. اینطوری O(n^2 log R) داریم! :) اگه اون فکت دور انداختن بزرگترین یال رو اثبات کردید ممنون می‌شم تو نظرات بگید!
