Sadə qabıq
Gari, sadə ortoqonal çoxbucaqlılar yaratmağa çalışırdı, lakin onun alqoritmi bəzi problemlərlə üzləşdi. Bir neçə saatlıq düzəlişdən sonra nəhayət problemin nə olduğunu anladı: görünür, onun yaratdığı çoxbucaqlılar öz-özünə kəsişmələrə malik ola bilərdi ki, bu da onun planlaşdırdığı şey deyildi!
Xüsusilə, Gari tərəfindən yaradılan “çoxbucaqlılar” n nöqtədən ibarət siyahı ilə təqdim olunur p[i] = (x[i], y[i]), bağlanmış çoxbucaqlı zəncir əmələ gətirir. Çoxbucaqlı zəncir öz-özünə kəsişmələrə malik ola bilər. Zəncirdəki hər iki ardıcıl nöqtə (x[i], y[i]) və (x[j], y[j]) ilə əmələ gələn seqmentlər ya şaquli, ya da üfüqi olur.
Test nümunələri üçün çoxbucaqlı zəncirlər aşağıda göstərilmişdir (miqyasda deyil):
Siz Gariyə bu problemi həll etməyə kömək etməyə qərar verdiniz, tamamilə zənciri əhatə edən və mümkün qədər kiçik sahəyə malik olan sadə (öz-özünə kəsişməyən) çoxbucaqlını hesablayaraq. Belə bir çoxbucaqlının sahəsi nə qədərdir?
Rəsmi olaraq, hər iki ardıcıl nöqtə p[i] və p[j] üçün [p[i], p[j]] seqmentlərini əhatə edən bütün sadə ortoqonal çoxbucaqlıların sahələrinin aşağı sərhədini hesablamalısınız.
Giriş Məlumatları
Birinci sətir təbii ədəd n (4 ≤ n ≤ 100 000) ehtiva edir. Növbəti n sətir çoxbucaqlının ətrafında (x[i], y[i]) nöqtələrini ehtiva edir (1 ≤ x[i], y[i] ≤ 10^6). Heç bir iki ardıcıl nöqtə üst-üstə düşmür və ardıcıl iki şaquli seqment və ya ardıcıl iki üfüqi seqment yoxdur.
Çıxış Məlumatları
Bütün bağlanmış çoxbucaqlı zənciri əhatə edən sadə çoxbucaqlıların sahələrinin dəqiq aşağı sərhədini göstərən bir qeyri-mənfi tam ədəd çıxarın. Cavabın həmişə tam ədəd olduğu sübut edilə bilər.
Nümunə
Nümunələrdə 1 və 3 üçün dəqiq olaraq 50 və 8 sahəyə malik sadə çoxbucaqlı yoxdur; lakin bu dəyərlərə istənilən qədər yaxın sahələrə malik sadə çoxbucaqlılar mövcuddur.