Bessie nghe một trận mưa sao băng phi thường sắp tới: chúng đâm xuống đất và hủy mọi thứ trúng phải. Lo an toàn, cô quyết tìm đường tới nơi an toàn, không bao giờ bị sao băng hủy. Đang gặm cỏ ở gốc tọa độ, cô muốn đi tới nơi mới an toàn hơn, tránh bị hủy trên đường.
Có $M$ sao băng rơi, $(1 \le M \le 50,000)$. Sao $i$ đâm vào $(X_{i}, Y_{i})$, $(0 \le X_{i} \le 300; 0 \le Y_{i} \le 300)$, lúc $T_{i}$, $(0 \le T_{i} \le 1,000)$. Hủy điểm đó và bốn điểm lưới kề ngang hoặc dọc.
Bessie rời gốc lúc $0$, đi trong góc phần tư thứ nhất song song trục với tốc độ một đơn vị khoảng cách mỗi giây tới điểm kề chưa bị hủy (thường bốn điểm). Không được ở một điểm vào lúc nó bị hủy hoặc sau đó.
Tìm thời gian nhỏ nhất tới nơi an toàn.
Dữ liệu vào
Đọc từ đầu vào chuẩn.
Dòng $1$: một số nguyên $M$.
Các dòng $2,\ldots,M+1$: dòng $i+1$ gồm ba số nguyên cách bằng khoảng trắng: $X_{i}$, $Y_{i}$, $T_{i}$.
Dữ liệu ra
Ghi ra đầu ra chuẩn.
- Dòng $1$: thời gian nhỏ nhất hoặc $-1$ nếu không thể.
Ví dụ
Dữ liệu vào 1
4 0 0 2 2 1 2 1 1 2 0 3 5
Dữ liệu ra 1
5
Ghi chú
Bốn sao đâm vào $(0, 0)$, $(2, 1)$, $(1, 1)$, $(0, 3)$ lần lượt lúc $2$, $2$, $2$, $5$.
t = 0 t = 2 t = 5 5|. . . . . . . 5|. . . . . . . 5|. . . . . . . 4|. . . . . . . 4|. . . . . . . 4|# . . . . . . * = sao băng va chạm 3|. . . . . . . 3|. . . . . . . 3|* # . . . . . 2|. . . . . . . 2|. # # . . . . 2|# # # . . . . # = đồng cỏ bị hủy 1|. . . . . . . 1|# * * # . . . 1|# # # # . . . 0|B . . . . . . 0|* # # . . . . 0|# # # . . . . -------------- -------------- -------------- 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6
Hình lúc $t=5$ có điểm an toàn gần nhất $(3, 0)$ nhưng sao thứ hai chặn đường quá sớm. Điểm kế $(4,0)$ cũng bị chặn quá sớm. Tiếp là điểm lưới trên đường chéo $(0,5)$-$(5,0)$. Trong đó $(0,5)$, $(1,4)$, $(2,3)$ đều tới được trong $5$ đơn vị thời gian.
5|. . . . . . .
4|. . . . . . .
3|3 4 5 . . . . vị trí Bessie theo thời gian
2|2 . . . . . . cho một lời giải
1|1 . . . . . .
0|0 . . . . . .
--------------
0 1 2 3 4 5 6Tác giả bài toán: Jeffrey Wang, 2007