2015
04-16

# The Voyages of Zheng He

Zheng He (1371�C1433) was a Hui-Chinese mariner, explorer, diplomat and fle et admiral, who commanded seven voyages to Southeast Asia, South Asia, the Middle East, and East Africa, collectively referred to as the Voyages of Zheng He.
His fle et was by far the largest and most advanced fleet in the world at his time, and his voyages were about 80 years earlier than Columbus’ America discovering voyage.
Recently some Chinese ACMers just found an old document about Zheng He’s Voyage. It said:
Once upon a time, when Zheng He was sailing along the Malaysia coast, a strange volcano suddenly erupted.The volcano threw some strange hot rocks on the sea. Those rocks floated on the water at first, and after some time, when water went into their center, they would explode. Every rock could be considered as a point and it had a set of properties X, Y, R, T and L, meaning that:
The position of the rock was (X, Y). The rock would explode at time T, and the explosion would last until time T+L. During the time interval [T, T+L](both ends are included), any ship whose distance from that rock was no more than R would be destroyed.
At time 0, Zheng He’s ship was at the position (0, 0), and his ship could also be considered as a point. When talking about "distance", it means the Manhattan Distance. In a plane, the Manhattan Distance between (x1, y1) and (x2, y2) is |x1 – x2| + |y1 – y2|. Zheng He’s ship could only move horizontally or vertically. The maximum speed of Zheng He’s ship was 1 per second. That means, if Zheng He’s ship was at (x, y) now, then 1 second latter it may arrive at any point in the region S( S={(x1,y1) | |x1-x|+|y1-y| <= 1}).
Suppose Zheng He knew every rock’s properties. Given time P, Zheng He wanted to know whether he could survive after time P.

Input contains several test cases. For each test case:
The first line contains 2 integers, N and P (1<=N<=1000,1<=P<=1000000), indicating that there were N rocks on the sea and Zheng He wanted to know whether he could survive after time P.
Then N lines follow. Each line describes a rock by 5 integers —- X, Y, R, T and L(-50<=X, Y<=50, 1<=R<=50, 1<=T, L<=10000) mentioned above.
Input ends with N = P = 0.

Input contains several test cases. For each test case:
The first line contains 2 integers, N and P (1<=N<=1000,1<=P<=1000000), indicating that there were N rocks on the sea and Zheng He wanted to know whether he could survive after time P.
Then N lines follow. Each line describes a rock by 5 integers —- X, Y, R, T and L(-50<=X, Y<=50, 1<=R<=50, 1<=T, L<=10000) mentioned above.
Input ends with N = P = 0.

4 30
50 50 50 50 100
-50 50 50 50 100
50 -50 50 50 100
-50 -50 50 50 100
3 20
-1 -4 4 3 7
-4 2 8 6 1
4 -3 10 10 10
0 0

Zheng can survive.
The survive area is : 1800.000
Zheng dies at : 10

1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

3. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。