E. Ангараг дээрх колони

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Дэлхийн нүүн суурьшигч нарыг тээвэрлэж буй эхний хөлөг Ангараг гариг дээр газарджээ. Колоничлогчид $n$ ширхэг барилга гаригийн гадаргуу дээр барих шаардлагатай гэж үзэж байв (гаригийг хавтгайгаар дүрслэх бөгөөд барилгуудыг уг хавтгай дээрх цэгүүдээр дүрсэлнэ). Гэвч нэгэн өдөр хайгуулчид колонийн зах хавиар сэжигтэй хөдөлгөөн илрүүлсэн бөгөөд иймд хамгаалалтын хүчний системийг хэрэглэн колонийн газрыг боломжит аюулаас хамгаалахаар болжээ.

Систем дараах байдлаар ажиллана: гаригийн гадаргуу дээр хэсэг тооны цахилгаан үүсвэрүүд оршин (эдгээрийг мөн адил цэгээр дүрсэлнэ) байна. Цахилгаан үүсгэвэр болгоны идэвхтэй тусгалын зай нь уг үүсгэвэр дээр төвтэй $r$ радиус бүхий тойрог байх юм (тойргийн ирмэг нь мөн уг тусгалын зайд орж байна). Систем идэвхжсэний дараа хамгаалалтын талбар нь зөвхөн гаригийн гадаргуун хэсэг газрыг л хамрах бөгөөд тодруулбал эдгээр цахилгаан үүсгэврүүдийн идэвхтэй тусгалын зай дотор байх газрыг хамгаалалтдаа авах ажээ. Өөрөөр хэлбэл хамгаалагдсан хэсэг гэдэг нь эдгээр цахилгаан үүсгэврүүдийн идэвхтэй тусгалын зайнуудын огтлолцол байх юм.

Колоничлогчид-ийн хэрэглэх цахилгаан үүсгэврийн тоонд хязгаар байхгүй боловч уг цахилгаан үүсгэврүүдийн систем нь маш их энерги шаардаж байв. Илүү тодруулбал энерги зарцуулалт нь цахилгаан үүсгэврийн тооноос хамаарахгүй боловч энэ нь системээр хамгаалагдаж буй хэсгийн талбайгаас шууд хамааралтай байх юм. Мөн түүнчлэн бүх барилгууд нь уг хамгаалагдсан хэсэг дотор байрласан байх шаардлагатай байв.

Тэгвэл бүх барилгуудыг агуулах хамгаалагдсан хэсгийн боломжит хамгийн бага талбайг олно уу.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $r$ ($1 ≤ n ≤ 10^{5}$, $1 ≤ r ≤ 50000$) өгөгдөх ба эдгээр нь харгалзан барилгуудын тоо болон цахилгаан үүсгэврүүдийн идэвхтэй тусгалын зайг тус тус илэрхийлнэ.

Дараагийн $n$ мөрөнд барилгуудын координатууд өгөгдөнө. $i + 1$-р мөрөнд ($1 ≤ i ≤ n$) таслалаас хойш 3-н орны нарийвчлал бүхий 2 бодит тоо $x_{i}$ болон $y_{i}$ ($|x_{i}|, |y_{i}| ≤ 50000$) өгөгдөх ба эдгээр нь $i$-р барилгын координатуудыг илэрхийлнэ. Түүнчлэн ямар ч 2 барилгууд нь нэг ижил цэг дээр байрлаагүй байх бөгөөд ямар ч 2 ялгаатай барилгуудын хоорондох зай $1$-ээс багагүй байна.

Мөн бүх барилгуудыг агуулах $r$ радиус бүхий тойрог заавал оршин байна.

Гаралт

Бүх барилгуудыг агуулах хамгаалагдсан хэсгийн боломжит хамгийн бага талбайг илэрхийлэх ганц бодит тоог хэвлэнэ үү. Хэрэв таны хариултын абсолют болон харьцангуй алдаа $10^{ - 4}$-өөс хэтрэхгүй байвал таны хариултыг зөвөөр тооцно.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3 5
0.00 0.000
0.0 8.00
6 8.00
Гаралт
78.5398163397
Оролт
4 1000
0.0 0.0
0 2.00
2.00 2
2.0 0.00
Гаралт
4.0026666140
Оролт
4 5
3.00 0.0
-3 0.00
0.000 1
0.0 -1.00
Гаралт
8.1750554397

Тэмдэглэл

Эхний жишээнд өгөгдсөн радиус нь бүх өгөгдсөн цэгүүдийг агуулах тойргийн радиустай тэнцүү байна. Ийм учраас уг тойрог нь бидний хайж буй хамгийн бага талбай болох ба бодлогын хариулт нь $25π$ болох юм.

2-дахь жишээнд бидний хайж буй талбай нь өгөгдсөн цэгүүд дээр оройтой квадратын талбайтай маш ойрхон байх юм.

3-дахь жишээний талбайг доорх зурагт дүрслэв:

Сэтгэгдлүүдийг ачааллаж байна...