Luyện Bắn II

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Nong dan John huan luyen ban cung cho $4 N$ con bo. Co $N$ bia hinh chu nhat can ban. Moi bia co 4 dinh, va moi con bo duoc gan voi mot dinh khac nhau.

Moi con bo dung tren truc $y$ (tai $x = 0$ ) va ban theo duong thang voi do doc $s_{i}$ . Moi mui ten di theo duong $y = s_{i} \cdot x + b$ (voi $b$ la vi tri cua bo tren truc $y$ ). Mot phat ban that bai neu mui ten di qua phan ben trong cua bia truoc khi den dinh duoc gan.

Tat ca cac bia co canh trai tai $x = X_{1}$ . Bia thu $i$ co goc duoi trai $(X_{1}, y_{1}^{(i)})$ va goc tren phai $(x_{2}^{(i)}, y_{2}^{(i)})$ .

Hay tim cach gan bo vao cac dinh va dat vi tri cac bo tren truc $y$ sao cho khoang cach giua hai bo xa nhat la nho nhat. In gia tri khoang cach nho nhat do, hoac $- 1$ neu khong the thuc hien.

Du lieu vao

Dong 1: So nguyen $T$ ( $1 \leq T \leq 10$ ) -- so test case.
Voi moi test case:
- Dong 1: Hai so nguyen $N$ va $X_{1}$ .
- $N$ dong tiep theo: Ba so nguyen $y_{1}^{(i)}$ , $y_{2}^{(i)}$ , $x_{2}^{(i)}$ .
- Dong cuoi: $4 N$ so nguyen la cac do doc $s_{1}, s_{2}, \dots, s_{4 N}$ .

Du lieu ra

Voi moi test case, in khoang cach nho nhat hoac $- 1$ .

Rang buoc

$1 \leq N \leq 4 \times 10^{4}$
Tong $N$ qua cac test case $\leq 4 \times 10^{4}$
$1 \leq X_{1} < x_{2}^{(i)} \leq 10^{9}$
$1 \leq y_{1}^{(i)} < y_{2}^{(i)} \leq 10^{9}$
$0 < | s_{i} | < 10^{9}$

Vi du

Input	Output	Giai thich
3 2 1 1 3 6 4 6 3 1 -1 2 -2 3 -3 4 -4 2 1 1 3 6 4 6 3 1 1 2 2 3 3 4 4 2 1 1 3 3 4 6 3 1 -1 2 -2 3 -3 4 -4	17 -1 11	Test 2: khong co do doc am, khong the ban vao goc tren phai.

Bình luận

Không có bình luận tại thời điểm này.