시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 11 | 2 | 2 | 18.182% |
Due to the increased robbing in the Silk route, the number of merchants travelling through the Silk route is getting less and less. Each robber at any place on the route requests money as much as possible from passing merchants. Now, merchants prefer not to travel through the Silk route even if their travel distances increase by choosing other routes. This has reduced the income of robbers and now Moradbeig, the cheif chair of the robbers, has been forced to set up a new robbing system, namely the toll system. Based on this system, each robber is restricted to a specific square-like area (including the boundary), so-called the robber territory, with no assumption on territories to be disjoint. More importantly, the toll fee is set to be exactly 1 Oshloob inside each territory. The other rules of the new system is listed below.
Marco Polo, a wealthy merchant, is planning to travel through the Silk route from the beginning to the end. Although the situation is better compared to the past, he still thinks of paying less toll. Your job is to write a program that computes the minimum toll that Marco Polo has to pay in order to traverse the whole route. For simplicity, you can assume the Silk route is a rectilinear path, i.e., each segment of the path is either horizontal or vertical.
There are multiple test cases in the input. Each test case starts with a line containing two positive integers n and m (n, m ⩽ 1000) which are the numbers of territories and the number of vertices of the Silk route, respectively. The next n lines describe the territories; one territory per line. Each line contains non-negative integers x, y and k (x, y ⩽ 106, k ⩽ 1000) where (x, y) is the lowest and leftmost corner of the territory and k is the side length of the territory. Each of the next m lines presents the coordinates of the vertices of the Silk route in the order of appearing on the route. It is guaranteed that the route does not intersect itself. The input terminates with a line containing 0 0 which should not be processed.
For each test case, output a line containing the minimum toll that must be paid by Marco Polo.
4 6 1 1 3 2 7 4 3 2 6 7 1 5 2 3 8 3 8 5 5 5 5 10 1 10 0 0
3
ICPC > Regionals > Asia West Continent > Iran > Tehran Site 2014 H번