Category
Similar Problems

0850. Masha va Maymoq 2

Time limit : 3000 ms
Memory limit : 64 mb

Xabaringiz bor Masha va Maymoq dehqonchilik bilan shug’ullanishadi. Ular bu yil tomorqalariga sabzi ekishdi. Hosil ancha yaxshi bo’ldi lekin quyon ularning hosiliga katta zarar yetkazdi.

Masha va Maymoq yangi yilda ham bu holat takrorlanmasligi uchun o’z tomorqalarini himoyalash choralarini izlashmoqda. Ularning tomorqasi qavariq ko’pburchak shaklida bo’lib n ta butun koordinatalardan o’tadi va tashqaridan hech qanday panjaralar bilan o’ralmagan. Ular tomorqasini panjaralar bilan o’rashni rejalashtirishmoqda. Ularning tomorqasi joylashgan hududda m ta daraxt bo’lib ular ham butun koordinatalarda joylashgan (daraxtlar tomorqa ichida va tashqarisida ham joylashishi mumkin). Ular panjaralarni shu daraxtlar orqali o’tkazishga qaror qilishdi (ya’ni panjaralar bilan o’ralgan hudud ham ko’pburchak shaklida bo’ladi). Lekin ularning panjaralari keragidan kamroq bo’lganligi uchun ular panjaralarni faqat tomorqaning aniq ichida (agar nuqta ko’pburchakning tomonlarida va tashqarisida yotmasa nuqta ko’pburchakning aniq ichida joylashgan deyiladi) joylashgan daraxtlar orqali o’tkazish fikrini ma’qullashmoqda. Ular maksimal yuzali hududni panjaralar bilan o’rashni hohlashadi. Ammo bu masalani ham mustaqil yecha olishmadi va har doimgiday dasturchilardan yordam so’rashga qaror qilishdi. Sizning vazifangiz Masha va Maymoq qanday maksimal yuzali hududni panjara bilan o’ray olishini topish.

 

Kiruvchi ma’lumotlar: Birinchi satrda bitta butun son n tomorqa joylashgan ko’pburchakning uchlari soni (3 ≤ n ≤ 105). Keyingi n satrda ikkitadan butun son xi, yi ko’pburchak nuqtalarining koordinatalari (-109 ≤ xi, yi ≤ 109). Ko’pburchak nuqtalari soat strelkasi yo’nalishida beriladi va uning ixtiyoriy 3 ta nuqtasi bir to’g’ri chiziqda yotmaydi.

Keyingi qatorda bitta butun son m daraxtlar soni (1 ≤ m ≤ 105). Keyingi m satrda ikkitadan butun son xi, yi daraxtlarning koordinatalari (-109 ≤ xj, yj ≤ 109). Daraxtlarning koordinatalari ustma-ust tushmaydi.

 

Chiquvchi ma’lumotlar: Bitta haqiqiy son panjara bilan o’ralgan hududning maksimal yuzasini 10-3.

 

№

Kiruvchi ma’lumotlar

Chiquvchi ma’lumotlar

1

4

-2 -2

-1 2

3 2

2 -2

4

0 2

0 0

2 1

2 -1

2.000

2

5

1 2

4 2

3 -3

-2 -2

-2 1

4

0 1

1 2

4 1

2 -1

0.000