#include #include #include #include struct Point{ int x, y; Point(int x_ = 0, int y_ = 0): x(x_), y(y_){} bool operator < (const Point & p) const { if(x != p.x){return x < p.x;} return y < p.y; } Point operator + (const Point & p) const { return Point(x + p.x, y + p.y); } bool operator == (const Point & p) const { return x == p.x and y == p.y; } }; typedef std::vector Body; struct State{ Body body; int distance; State(const Body & b, int d): body(b), distance(d){} }; std::set visited_bodies; bool touches(const Point & p, const Point & q){ return abs(p.x - q.x) <= 1 and abs(p.y - q.y) <= 1 and abs(p.x - q.x + p.y - q.y) != 2; } void addNewStates(std::deque & q, Body & body, int distance, const std::set & rocks, int depth, bool previous){ if(depth == body.size()){ if(visited_bodies.insert(body).second){ q.push_back(State(body, distance)); } return; } const Point dp[] = {Point(0, -1), Point(1, -1), Point(1, 0), Point(0, 1), Point(-1, 1), Point(-1, 0)}; if(not previous){ Point save = body[depth]; for(int i = 0; i < 6; i++){ body[depth] = save + dp[i]; if(depth > 0 and not touches(body[depth], body[depth - 1])){continue;} if(depth < body.size() - 1 and not touches(body[depth], body[depth + 1])){continue;} bool ok = rocks.find(body[depth]) == rocks.end(); for(int j = 0; j < depth - 1 && ok; j++){ ok = not (body[depth] == body[j]) and not touches(body[depth], body[j]); } if(ok){addNewStates(q, body, distance, rocks, depth + 1, true);} } body[depth] = save; } if(depth > 0 and not touches(body[depth], body[depth - 1])){return;} bool ok = true; for(int j = 0; j < depth - 1 && ok; j++){ ok = not (body[depth] == body[j]) and not touches(body[depth], body[j]); } if(ok){addNewStates(q, body, distance, rocks, depth + 1, false);} } int main(){ while(true){ int n, k, x, y; Point destination; Body body; std::set rocks; std::cin >> n; if(n == 0){break;} for(int i = 0; i < n; i++){ std::cin >> x >> y; body.push_back(Point(x, y)); } std::cin >> k; for(int i = 0; i < k; i++){ std::cin >> x >> y; rocks.insert(Point(x, y)); } std::cin >> destination.x >> destination.y; std::deque q; visited_bodies.clear(); q.push_back(State(body, 0)); while(true){ Body body = q.begin()->body; int distance = q.begin()->distance; if(body[0] == destination){ std::cout << distance << std::endl; break; } q.pop_front(); addNewStates(q, body, distance + 1, rocks, 0, false); } } }