Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT016F - ACM PTIT 2016 F - Di chuyển con xe

Xét lưới ô vuông vô hạn trong đó có một số ô cấm, các ô còn lại là tự do. Các dòng và cột của lưới được đánh số theo thứ tự bởi các số nguyên … -3 -2 -1 0 1 2 3 … Các cột được đánh số theo thứ tự từ trái sang phải, còn các dòng theo thứ tự từ dưới lên trên. Ô nằm trên giao của dòng x và cột y được gọi là ô (x, y). Đặt một con xe vào ô xuất phát là một ô nào đó của lưới. Sau một bước đi, ta có thể di chuyển con xe đến một ô tự do bất kỳ nằm trên cùng một dòng hoặc cột với nó, miễn là giữa ô xuất phát và ô đích trên cùng dòng hoặc cột không có ô cấm.

Yêu cầu: Cho biết toạ độ của các ô cấm, vị trí ô xuất phát đặt con xe và vị trí ô đích nơi con xe cần đến, hãy tìm cách di chuyển con xe từ ô xuất phát đến ô đích sao cho số lượng bước đi cần thực hiện là ít nhất.

Input

 

Dòng đầu tiên chứa T (T ≤ 10) là số lượng test, tiếp đến là T nhóm dòng, mỗi nhóm chứa dữ liệu về một test theo khuôn dạng sau: 
Dòng đầu tiên chứa 4 số nguyên xs, ys, xt, yt được ghi cách nhau bởi dấu cách cho biết toạ độ của ô xuất phát là (xs, ys) và ô đích là (xt, yt);
Dòng thứ hai chứa số nguyên dương n (n ≤ 1000) là số lượng ô cấm;
Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên được ghi cách nhau bởi dấu cách xi, yi cho biết (xi, yi) là toạ độ của ô cấm thứ i (i = 1, 2, …, n). 
Giả thiết là −109 ≤ xs, ys, xt, yt ≤ 109 ;  −109 ≤ xi, yi ≤ 109

Dòng đầu tiên chứa T (T ≤ 10) là số lượng test, tiếp đến là T nhóm dòng, mỗi nhóm chứa dữ liệu về một test theo khuôn dạng sau:

·        Dòng đầu tiên chứa 4 số nguyên xs, ys, xt, yt được ghi cách nhau bởi dấu cách cho biết toạ độ của ô xuất phát là (xs, ys) và ô đích là (xt, yt);

·        Dòng thứ hai chứa số nguyên dương n (n ≤ 1000) là số lượng ô cấm;

·        Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên được ghi cách nhau bởi dấu cách xi, yi cho biết (xi, yi) là toạ độ của ô cấm thứ i (i = 1, 2, …, n).

Giả thiết là 109xs, ys, xt, yt ≤ 10109xi, yi ≤ 109

 

Output

·        Gồm T dòng mỗi dòng chứa kết quả của một test tương ứng trong dữ liệu vào là số lượng bước đi ít nhất cần thực hiện để di chuyển con xe từ ô xuất phát đến ô đích. Ghi số −1 nếu như không thể di chuyển con xe đến ô đích. 

Example

Test 1:

Input:

1

1 –1 5 -4 

1 1 

5 –5 

2 –4 

4 –1

Output:
3
Test 2:
Input:
1
10 11 5001 -4733 
5001 -4732 
5001 –4734 
1 1 
5000 –4733 
5002 –4733
Output:
-1
Hình vẽ minh họa cho ví dụ 1:

Được gửi lên bởi:adm
Ngày:2016-04-26
Thời gian chạy:1s-3s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2016-11-28 16:37:12
Đường đi giống với trò game Lines98 huyền thoại
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.