B. Уулзалт

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

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

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

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

Сүпер Дүпер цэргийн салааны Сүпер Дүпер нууц уулзалт нь нэгэн Сүпер Дүпер нууц газар зохиогдохоор болжээ. Уг газар нь декартын координатын систем дээрх хязгааргүй хавтгайгаар дүрслэгдэх ажээ. Уулзалтын ширээ нь талууд нь координатын тэнхлэгүүдтэй параллель байх тэгш өнцөгтөөр дүрслэгдэх бөгөөд уг тэгш өнцөгтийн оройнууд нь хавтгай дээрх бүхэл тоон цэгүүд дээр байрласан байв. Мөн ширээний периметр дээр оршин байх(өөрөөр хэлбэл ширээний ирмэг дээр оршин байх) бүхэл тоон цэг болгон дээр генералын сандал оршин байх юм.

Хавтгай дээр байрлах зарим цэгүүд дээр генералуудыг өвлийн хүйтэнд дааруулахгүйн тулд паарнуудыг байрлуулсан байв. Паар болгон нь $r_{i}$ гэсэн тоогоор дүрслэгдэх бөгөөд энэ нь уг паарны халааж чадах талбайн радиусыг илэрхийлэх юм. Өөрөөр хэлбэл хэрэв ямар нэгэн генерал болон өгөгдсөн паар 2-ын хоорондох зай нь $r_{i}$-аас бага буюу тэнцүү байвал генерал маш тухтай бөгөөд дулаахан байх ажээ. Энд зайг тодорхойлохдоо Эвклидийн зайг ашиглах бөгөөд иймд $(x_{1}, y_{1})$ болон $(x_{2}, y_{2})$ гэсэн 2 цэгийн хоорондох зай нь -тай тэнцүү байна.

Паарны халаах талбайгаас гадуур байрласан генерал болгон нь өвдөх ажээ. Иймд та тэдгээр генералуудад зориулан дулаан хөнжил авчрах ёстой байв. Таны даалгавар бол уг Сүпер Дүпер нууц газарт авчрах ёстой дулаан хөнжлийн тоог олох юм.

Аль хэдийн тухтай байгаа генералуудад хөнжил хэрэггүй байна. Мөн генералууд нь хэзээ ч халууцна гэж үзэхгүй. Хэрэв тэд хэд хэдэн паарны халаах талбайд байсан ч тэднийг халууцна гэж үзэхгүй юм. Паарнууд нь хавтгай дээрх ямар ч бүхэл тоон цэгүүд дээр байрласан байж болох бөгөөд тэгш өнцөгт дотор ч (ширээний доор), периметр дээр ч хүртэл (ямар нэгэн генералын яг доор) байрласан байж болно. Эдгээр тохиолдлуудад хүртэл радиусууд нь өөрчлөгдөхгүй байх юм.

Оролт

Оролтын эхний мөрөнд ширээний эсрэг 2 булангуудын координатууд $x_{a}$, $y_{a}$, $x_{b}$, $y_{b}$ ($x_{a} ≠ x_{b}, y_{a} ≠ y_{b})$-ууд өгөгдөнө. 2-дахь мөрөнд бүхэл тоо $n$ өгөгдөх ба энэ нь нийт паарнуудын тоог ($1 ≤ n ≤ 10^{3}$) илэрхийлнэ. Дараагийн $n$ ширхэг мөрөнд паарнуудын координатууд нь "$x_{i}$ $y_{i}$ $r_{i}$" хэлбэртэйгээр өгөгдөх ба эдгээр тоонууд нь зайгаар тусгаарлагдсан байна. Оролтод өгөгдөх бүх тоонууд нь бүхэл тоонууд байх бөгөөд бүх координатуудын абсолют утга нь $1000$-аас хэтрэхгүй байна, $1 ≤ r_{i} ≤ 1000$. Түүнчлэн хэд хэдэн паарнууд нэг ижил цэг дээр байрласан байж болно.

Гаралт

Таны авчрах ёстой хөнжлийн тоог хэвлэнэ үү.

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

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

Оролт
2 5 4 2
3
3 1 2
5 3 1
1 3 2
Гаралт
4
Оролт
5 2 6 3
2
6 2 2
6 5 3
Гаралт
0

Тэмдэглэл

Эхний жишээнд генералуудын сууж буй цэгүүд нь: $(2, 2)$, $(2, 3)$, $(2, 4)$, $(2, 5)$, $(3, 2)$, $(3, 5)$, $(4, 2)$, $(4, 3)$, $(4, 4)$, $(4, 5)$ байна. Эдгээрийн дундаас 4-н ширхэг генерал нь паарнуудын халаах талбайгаас гадна сууж байгаа юм. Эдгээр генералуудын байрлах цэгүүд нь: $(2, 5)$, $(3, 5)$, $(4, 4)$, $(4, 5)$ байна.

2-дахь жишээнд генералуудын сууж буй цэгүүд нь: $(5, 2)$, $(5, 3)$, $(6, 2)$, $(6, 3)$ байна. Түүнчлэн эдгээр бүх генералууд нь халаалттай талбай дотор сууж байгаа юм.

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