D. Гүүр барих

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

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

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

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

Хоёр тосгон хоорондоо хойноос урд зүгт урсдаг голоор тусгаарлагдана. Тосгоны оршин суугчид тосгод хооронд хялбар дамжихын тулд голыг хөндлөн гарсан гүүр барихыг хүсч байна.

Голын эргүүдийг $x = a$ ба $x = b$ ($0 < a < b$) босоо шугамнууд гэж үзэж болно.

Баруун тосгон хээр тал дахь $O = (0, 0)$ цэг дээр байдаг. Энд $A_{i} = (a, y_{i})$ цэгүүд дээр төгсгөлтэй тосгоноос гол хүрсэн $n$ жим байдаг. Тосгоны оршин суугчид энгийн, хялбар хүмүүс учраас тэдний зам нь шулуун байдаг.

Зүүн тосгоны хүмүүс хашир, зальтай. Тэдний тосгон голын зүүн эрэг дээрх ойд байдаг боловч тосгоны нарийн байрлал тодорхой бус. Энд $B_{i} = (b, y'_{i})$ цэгүүд дээр төгсгөлтэй тосгоноос гол хүрсэн $m$ мушгирсан зам байна. Эдгээр замуудын урт мэдэгдэх ба зүүн тосгоноос $B_{i}$ цэг хүрсэн замын урт $l_{i}$ байна.

Тосгоны оршин суугчид голын зүүн эрэгт яг нэг $A_{i}$ цэг болон баруун эрэгт яг нэг $B_{j}$ цэг сонгох ба тэдгээрийн холбосон шулуун гүүр барихыг хүсч байна. Энд тосгодын хоорондын зайг ($|OA_{i}| + |A_{i}B_{j}| + l_{j}$ нийлбэр ба энд $|XY|$ нь $X$ ба $Y$ цэгүүдийн хоорондох Эвкледийн зай юм) хамгийн бага байлгахыг зорино. $(x_{1}, y_{1})$ ба $(x_{2}, y_{2})$ цэгүүдийн хоорондох Эвкледийн зай нь тэнцүү байна.

Тэдэнд шаардлагатай хос цэгийг олж өгч туслана уу.

Оролт

Эхний мөрөнд $n$, $m$, $a$, $b$ ($1 ≤ n, m ≤ 10^{5}$, $0 < a < b < 10^{6}$) бүхэл тоонууд байна.

Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ бүхэл тоо өсөх эрэмбээр байх ба $i$-р бүхэл тоо нь $A_{i}$ цэгийн координатыг тодорхойлох ба $y_{i}$ ($|y_{i}| ≤ 10^{6}$) байна.

Гурав дахь мөрөнд $m$ бүхэл тоо өсөх эрэмбээр байх ба $i$-р бүхэл тоо нь $B_{i}$ цэгийн координатыг тодорхойлох ба $y'_{i}$ ($|y'_{i}| ≤ 10^{6}$) байна.

Дөрөвдүгээр мөрөнд $m$ бүхэл тоо байх ба $i$-р бүхэл тоо нь зүүн тосгон ба $B_{i}$ цэгийн хоорондох зайг илэрхийлэх ба $l_{i}$ ($1 ≤ l_{i} ≤ 10^{6}$) байна.

Бүх $i$-н $(1 ≤ i ≤ m)$ хувьд $|B_{i}C| ≤ l_{i}$ байх X-тэнхлэг дээр байх $C$ цэг ядаж $b$ байх нь тодорхой. Энэ нь ямар ч хоёр $A_{i}$ цэг давхцахгүй мөн ямар ч хоёр $B_{i}$ цэг давхцахгүй гэсэн үг.

Гаралт

Хоёр тоо хэвлэх ба харгалзан та хооронд нь гүүр барих шаардлагатай зүүн болон баруун эрэг дээрх цэгүүдийн тоо байна. Та баруун эрэг дээрх цэгүүдийг оролтонд өгсөн дарааллаараа $1$-c $n$ хүртэл дугаарлагдсан гэж үзэж болно. Үүнтэй адилаар зүүн эрэг дээрх цэгүүд оролтонд өгсөн дарааллаараа $1$-c $m$ хүртэл дугаарлагдсан гэж үзэж болно.

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

Орчуулсан: Г.Мэндбаяр

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

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