Đi Dọc Hàng Rào

Đ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

Hàng rào của Farmer John gồm $P$ cọc ( $4 \leq P \leq 2 \times 10^{5}$ , $P$ chẵn) tại các tọa độ 2D phân biệt $(x, y)$ với $0 \leq x, y \leq 1000$ . Các cọc được nối bởi các đoạn thẳng ngang hoặc dọc tạo thành một đa giác kín vuông góc (rectilinear polygon). Các đoạn hàng rào chỉ giao nhau tại điểm đầu mút.

$N$ con bò ( $1 \leq N \leq 10^{5}$ ) mỗi con đi dạo dọc hàng rào từ một vị trí bắt đầu đến một vị trí kết thúc. Vì hàng rào là vòng kín, có hai hướng đi. Mỗi con bò sẽ đi theo hướng ngắn hơn (nếu bằng nhau, bò có thể chọn hướng bất kỳ).

Hãy tính quãng đường mỗi con bò đi.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $P$
$P$ dòng tiếp: Hai số nguyên $x$ , $y$ -- tọa độ mỗi cọc (theo thứ tự quanh hàng rào)
$N$ dòng tiếp: Bốn số nguyên $x_{1}$ , $y_{1}$ , $x_{2}$ , $y_{2}$ -- vị trí bắt đầu và kết thúc của mỗi con bò

Dữ liệu ra

$N$ dòng, mỗi dòng một số nguyên -- quãng đường mỗi con bò đi.

Ràng buộc

$1 \leq N \leq 10^{5}$
$4 \leq P \leq 2 \times 10^{5}$ , $P$ chẵn
$0 \leq x, y \leq 1000$
Test 2-6: $0 \leq x, y \leq 100$ và $N \leq 100$

Ví dụ

Input	Output	Giải thích
5 4 0 0 2 0 2 2 0 2 0 0 0 2 0 2 1 0 2 1 0 2 1 0 1 2 1 2 1 0	2 3 3 4 4	Hàng rào hình vuông cạnh 2, chu vi 8. Bò 1 đi từ (0,0) đến (0,2), quãng đường ngắn nhất là 2.

Bình luận

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