
ZOJ Problem Set  3376
Himekaidou Hatate (姫海棠はたて) is a crow tengu with the ability of spirit photography. The newspaper she writes, Kakashi Spirit News (「花果子念報」) is much less popular than Shameimaru Aya's Bunbunmaru News (「文々。新聞」). In order to beat Aya, Hatate decides to report Toramaru Shou, the disciple of Bishamonten (多闻天王). But it's not easy to take pictures of Shou and her bullet patterns while avoiding them as well. Assum that both Hatate and Shou stay in a w*h grid region. Shou fire lasers out in straight lines, the ith laser starts at (x_{i}, y_{i}) and moves in direction (dx_{i}, dy_{i}). The Manhattan distance of any two points (x1, y1) and (x2, y2) is x1  x2 + y1  y2. Any point with a Manhattan distance to some laser that is less that 1 is called dangerous point. All other points are safe points. The points which have maximum Manhattan distance to dangerous points is called safest points. Hatate hopes that a new feature can be added to her camera  for each senario, finding out the safest points quickly. You're asked to develop this feature. InputThere are multiple cases. Each one describes a senario. The first line is "w h n", where 3 ≤ w, h ≤ 1000 and 1 ≤ n ≤ 1000 is the number of lasers. The i+1th line is the ith laser "x_{i} y_{i} dx_{i} dy_{i}", where 0 ≤ x_{i} < w, 0 ≤ y_{i} < h, dx_{i}^{2} + dy_{i}^{2} > 0. Process to the each of file. OutputFor each case, output all safest points seperated by a single blank in lexicographic order. If there are no safe points, output "MISS!" instead. Sample Input3 3 3 0 0 2 1 0 1 2 1 0 2 2 2 4 4 2 0 0 3 3 3 0 1 1 5 5 2 4 4 1 1 0 4 2 2 Sample OutputMISS! (0, 1) (0, 2) (1, 0) (1, 3) (2, 0) (2, 3) (3, 1) (3, 2) (0, 2) (2, 0) (2, 4) (4, 2) Hint
ReferencesAuthor: WU, Zejun Source: ACM × Touhou Contest: ZOJ Monthly, August 2010 