Termit

Masala tavsifi

Termit taxtada, konveks ko'p burchak shaklida joylashgan. U qarab turgan tomonga to'g'ri harakat qiladi, lekin qaysi tomonga ekanligini bilmaydi. Agar u taxtaning chetiga yetib kelsa, u tushib ketadi. Termitning joylashuvi va ko'p burchakni tashkil etuvchi burchaklarning joylashuvlarini hisobga olib, u taxtadan tushib ketishidan oldin o'tishi mumkin bo'lgan eng qisqa masofani aniqlang. Barcha joylashuvlar 2D koordinatalarda berilgan.

Kirish ma'lumotlari

Birinchi qatorda ikki butun son $x$ va $y$ berilgan, ular Termitning koordinatalarini ifodalaydi ($-100 \le x \le 100$, $-100 \le y \le 100$).

Ikkinchi qatorda butun son $N$ berilgan, bu ko'p burchakning burchaklari sonini ifodalaydi ($3 \le N \le 10$).

Keyingi $N$ qatorlarda butun sonlar $x_i$ va $y_i$ ($-100 \le x_i, y_i \le 100$) berilgan, bu ko'p burchakning burchaklarining koordinatalarini ifodalaydi, soat yo'nalishiga qarshi tartibda berilgan.

Barcha kirish qiymatlari butun sonlardir. Nuqta $(x,y)$ kafolatlangan ravishda ko'p burchak ichida joylashgan (chetda emas) va ko'p burchak kafolatlangan ravishda konveksdir.

Chiqish ma'lumotlari

Termit taxtadan tushib ketishidan oldin o'tishi mumkin bo'lgan eng qisqa masofani bir qatorda chiqarib bering. Chiqarish qabul qilinadi, agar mutlaq xato yoki nisbiy xato $10^{-6}$ dan oshmasa.

Baholash tizimi

0 0
4
100 100
-100 100
-100 -100
100 -100

100

10 10
3
0 100
-100 -100
100 -100

31.3049516850

34 6
7
-43 -65
-23 -99
54 -68
65 92
16 83
-18 43
-39 2

25.0284205314