E. Баярын жагсаал

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

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

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

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

Берланд дахь агуу ялалтын тэмдэглэлт ой болгон нь заавал дайны баярын жагсаалтай болдог байв. Энэ жил ч мөн адил баярын жагсаал болох ажээ. Иймд уг жагсаалын бэлтгэлийг бүхий л хүчээ дайчлан бэлдэж байлаа. Танкууд нэг шугам үүсгэн байрлаж, их бууны анги буудахад бэлэн байх бөгөөд цэргүүд төв талбай дээр марш алхаа хийж байв... Харин агаарын хүчний генерал Ноён Женералов дахин асуудалд оржээ. Энэ жил маш олон тооны тэнгэр баганадсан барилгууд баригдсан бөгөөд эдгээр нь хотын дээгүүр онгоцоор нислэг хийхэд хүндрэл учруулж байв. Мөн онгоцнууд нь урд зүгээс хойд зүг хүртэл чиглэлд нислэг хийх ёстой хэмээн шийдсэн байжээ. Түүнчлэн ямар нэгэн онгоцны явах чиглэлд ямар ч тэнгэр баганадсан барилгууд байх ёсгүй бөгөөд хэрэв ямар нэгэн барилга байвал уг ойн баяр нь эмгэнэлт явдлаар төгсөх юм. Барилга Хотжилтын яам $n$ ширхэг тэнгэр баганадсан барилгуудын мэдээллийг өгчээ(бусад барилгуудыг маш жижиг гэж үзэх бөгөөд онгоцнуудад ямар нэгэн асуудал учруулахгүй гэж үзэх юм). Хотыг урдаас нь хойд хүртэл геометрийн хавтгай гэж дүрслэн харвал $i$-р барилга нь $h_{i}$ өндөртэй нэгэн тэгш өнцөгт байх юм. Түүнчлэн уг барилгын хамгийн баруун талд байрлах цэгийн x координат нь $l_{i}$ байх бөгөөд хамгийн зүүн талд байрлах цэгийн x координат нь $r_{i}$ байх ажээ. Уг талбайн газар нутаг нь хавтгай учраас бүх барилгууд нь газар зүйн нэг төвшинд баригдсан байх юм(өөрөөр хэлбэл тэгшхэн газар дээр бүх барилгууд нь баригдсан байна гэсэн үг юм). Та Батлан Хамгаалах яамны ахлах программистын хувьд эдгээр тэнгэр баганадсан барилгуудын мэдээллийг ашиглан эдгээр барилгуудын бүрхэх поли-хэрчим(олон тооны хэрчим)-ийг олох ёстой болжээ. Поли-хэрчмийн шинж чанар нь дараах байдалтай байна:

  • Хэрэв та хотыг урдаас нь хойд хүртэл геометрийн хавтгай гэж дүрслэн харвал, ямар ч барилгын ямар ч хэсэг нь поли-хэрчим болон газрын гадаргын үүсгэж буй талбайн дотор эсвэл ирмэг дээр байрласан байх юм. Тодруулга: поли хэрчим гэдэг нь хэд хэдэн хэрчмийг нийтэд нь хэлэх бөгөөд эдгээр хэрчмүүд болон газрын гадарга(өөрөөр хэлбэл координатын хавтгайн х тэнхлэг) 2-ын үүсгэх нэгэн талбай дотор бүх барилгууд нь багтаж байх юм.
  • Поли-хэрчим нь газрын төвшнөөс эхлэх бөгөөд төгсөх юм. Өөрөөр хэлбэл 0 өндөртэй газраас эхэлнэ(х тэнхлэгээс эхэлнэ гэсэн үг).
  • Поли-хэрчмийн хэрчмүүд нь координатын тэнхлэгүүдтэй параллель байна. Өөрөөр хэлбэл зөвхөн босоо эсвэл хөндлөн хэрчмүүд байх юм.
  • Поли-хэрчмийн оройнууд нь заавал бүхэл тоон координаттай байна.
  • Хэрэв та хотыг урдаас нь хойд хүртэл харвал поли-хэрчим нь (газрын гадаргатай хамт) заавал боломжит хамгийн бага талбайг бүрхсэн байна.
  • Поли-хэрчим нь заавал бүх поли-хэрчмүүд дундаас хамгийн бага урттай нь байх ёстой бөгөөд газрын гадаргатай хамт боломжит хамгийн бага талбайг бүрхсэн байх юм.
  • Поли-хэрчмийн дараалсан хэрчмүүд нь заавал хоорондоо перпендикуляр байна.

Уг зурагт 2-дахь жишээг дүрслэв(бүрхэж буй поли-хэрчмийг баруун талын зурагт тэмдэглэв).

Оролт

Оролтын эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 100000$) өгөгдөнө. Дараа нь $n$ ширхэг мөр өгөгдөх ба мөр болгонд 3-н ширхэг бүхэл тоо $h_{i}$, $l_{i}$, $r_{i}$ ($1 ≤ h_{i} ≤ 10^{9},  - 10^{9} ≤ l_{i} < r_{i} ≤ 10^{9}$)-ууд өгөгдөнө.

Гаралт

Гаралтын эхний мөрөнд бүхэл тоо $m$-г хэвлэх ба энэ нь бүрхэж буй поли-хэрчмийн оройн тоог илэрхийлнэ. Дараагийн $m$ мөрийн мөр болгонд 2 ширхэг бүхэл тоо хэвлэх бөгөөд эдгээр нь поли-хэрчмийн оройн байрлал болон өндрийг илэрхийлэх юм. Поли-хэрчмийг баруунаас зүүн хүртэл туулах дарааллын дагуу орой болгоны координатуудыг хэвлэнэ үү. Поли-хэрчмийн эхний болон сүүлийн оройнууд нь 0 өндөртэй байхыг анхаарна уу.

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

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

Оролт
2
3 0 2
4 1 3
Гаралт
6
0 0
0 3
1 3
1 4
3 4
3 0
Оролт
5
3 -3 0
2 -1 1
4 2 4
2 3 7
3 6 8
Гаралт
14
-3 0
-3 3
0 3
0 2
1 2
1 0
2 0
2 4
4 4
4 2
6 2
6 3
8 3
8 0
Сэтгэгдлүүдийг ачааллаж байна...