| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P133SUMC - SUM3 C - Bẫy ếch |
Nạn dịch ếch phá hoại mùa màng đang bắt đầu ở vùng quê của Tí và Tèo. Hai bạn quyết định đi đặt các bẫy ếch trên các thửa ruộng của gia đình mình. Dĩ nhiên, các con ếch cũng đủ thông minh để tránh xa các bẫy càng xa càng tốt.
Cánh đồng có dạng hình chữ nhật. Các con ếch nhảy theo hướng song song với cạnh của cánh đồng và mỗi bước nhảy có độ dài 1 đơn vị. “Khoảng cách bẫy ếch” với một hành trình của con ếch là khoảng cách ngắn nhất từ các điểm trên hành trình tới bẫy ếch gần nhất. Tí và Tèo đã biết trước điểm bắt đầu và điểm kết thúc thường xuyên nhất của các con ếch, và hai bạn đã thử nghiệm rất nhiều cách đặt bẫy ếch.
Các bạn hãy giúp Tí và Téo tính khoảng cách lớn nhất có thể của “khoảng cách bẫy ếch”.
Input
Dòng đầu tiên là 2 số wx và wy– tọa độ góc trên trái, giới hạn của cánh đồng .
(2 <= wx, wy <= 1 000). Tọa độ góc dưới phải là (1,1).
Dòng thứ hai gồm 4 số pz, py, kx và ky là tọa độ điểm bắt đầu điểm kết thúc của ếch.
(1 <= px, kx <= wx, 1 <= py, ky <= wy).
Tiếp theo là số bẫy ếch n (n <= 10^6).
n dòng tiếp theo là tọa độ (xi, yi) của các bẫy ếch.
Không có 2 bẫy ếch nào ở cùng vị trí và không có bẫy nào ở điểm (px, py) hoặc (kx, ky).
Output
Một số nguyên duy nhất là bình phương “khoảng cách bẫy ếch” lớn nhất.
Nếu con ếch buộc phải nhảy vào một bẫy ếch nào đó, đáp án ghi 0.
Example
Test 1:
Input:
5 5
1 1 5 5
2
3 3
4 2 Output:
4
Giải thích test 1:
Test 2:
Input:
4 4
1 1 1 1
3
1 4
4 1
3 3
Output:
8
| Được gửi lên bởi: | adm |
| Ngày: | 2013-07-25 |
| Thời gian chạy: | 5s |
| 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 JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
