Codeforces Round #803 (Div. 2)
05:35:06 |
Codeforces Round #804 (Div. 2)
6 өдрийн дараа |
B. Олон өнцөгтүүд
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Танд өөр нэгэн геометрийн бодлого өгөгджээ. Уг бодлогод танд 2 ширхэг үл гажуудсан $A$ болон $B$ олон өнцөгтүүд оройн координатуудаараа өгөгдөнө. $A$ олон өнцөгт нь заавал гүдгэр байна. $B$ нь өөртэйгөө огтлолцоогүй бөгөөд өөртэйгөө шүргэлцээгүй дурын олон өнцөгт байна. 2 олон өнцөгтийн оройнууд нь цагийн зүүний дагуу дарааллаар өгөгдөнө. Олон өнцөгт бүрийн хувьд ямар ч дараалсан 3 оройнууд нь нэг ижил шулуун дээр байрлаагүй байх юм.
Таны даалгавар бол $B$ олон өнцөгт нь $A$ олон өнцөгтийн яг дотор байрлаж байгаа эсэхийг шалгах юм. Энэ нь $B$ олон өнцөгтийн ямар ч цэг нь $A$ олон өнцөгтийн яг дотор нь байх ёстой гэсэн үг юм. Яг гэдэг нь $B$ олон өнцөгтийн орой нь $A$ олон өнцөгтийн тал дээр байж болохгүй гэсэн үг юм.
Оролт
Эхний мөрөнд $A$ олон өнцөгтийн оройнуудын тоо болох бүхэл тоо $n$ ($3 ≤ n ≤ 10^{5}$) өгөгдөнө. Дараагийн $n$ мөрөнд хос бүхэл тоонууд $x_{i}, y_{i}$ ($|x_{i}|, |y_{i}| ≤ 10^{9}$) өгөгдөх ба энэ нь $A$ олон өнцөгтийн $i$-дахь оройн координатуудыг илэрхийлнэ. Оройнууд нь цагийн зүүний дагуу дарааллаар өгөгдөнө.
Дараагийн мөрөнд $B$ олон өнцөгтийн оройнуудын тоо болох бүхэл тоо $m$ ($3 ≤ m ≤ 2*10^{4}$) өгөгдөнө. Дараагийн $m$ мөрөнд хос бүхэл тоонууд $x_{j}, y_{j}$ ($|x_{j}|, |y_{j}| ≤ 10^{9}$) өгөгдөх ба энэ нь $B$ олон өнцөгтийн $j$-дахь оройн координатуудыг илэрхийлнэ. Оройнууд нь цагийн зүүний дагуу дарааллаар өгөгдөнө.
Олон өнцөгтийн оройнуудын координатууд нь нэг зайгаар тусгаарлагдсан байна. $A$ болон $B$ олон өнцөгтүүд нь үл гажуудсан байх ба $A$ олон өнцөгт нь заавал гүдгэр байх бөгөөд $B$ олон өнцөгт нь өөртэйгөө огтлолцоогүй мөн өөртэйгөө шүргэлцээгүй байна. Олон өнцөгт бүрийн хувьд ямар ч дараалсан 3 оройнууд нь нэг ижил шулуун дээр байрлаагүй байна.
Гаралт
Бодлогын хариултыг ганц мөрөнд хэвлэх ба хэрэв $B$ олон өнцөгт нь $A$ олон өнцөгтийн яг дотор нь байвал "$YES$" бусад тохиолдолд "$NO$" гэж хэвлэнэ үү (хашилтгүйгээр).
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
6 -2 1 0 3 3 3 4 1 3 -2 2 -2 4 0 1 2 2 3 1 1 0
Гаралт
YES
Оролт
5 1 2 4 2 3 -3 -2 -2 -2 1 4 0 1 1 2 4 1 2 -1
Гаралт
NO
Оролт
5 -1 2 2 3 4 1 3 -2 0 -3 5 1 0 1 1 3 1 5 -1 2 -1
Гаралт
NO