#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 && y == p.y; } }; typedef std::vector Body; struct State{ Body body; int distance; State(const Body & b, int d): body(b), distance(d){} }; std::vector patterns[20]; bool touches(const Point & p, const Point & q){ static Point dp[] = {Point(0, -1), Point(1, -1), Point(1, 0), Point(0, 1), Point(-1, 1), Point(-1, 0)}; for(int k = 0; k < 6; k++){ if(p + dp[k] == q){return true;} } return false; } void addNewStates(std::list & q, Body & body, int distance, const std::set & rocks, int pattern, int depth){ if(depth == body.size()){ q.push_back(State(body, distance)); return; } static Point dp[] = {Point(0, -1), Point(1, -1), Point(1, 0), Point(0, 1), Point(-1, 1), Point(-1, 0)}; if((pattern >> depth) & 1){ 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 touches(body[depth], body[j]) and not (body[depth] == body[j]); } if(ok){ addNewStates(q, body, distance, rocks, pattern, depth + 1); } } body[depth] = save; }else{ 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 touches(body[depth], body[j]) and not (body[depth] == body[j]); } if(ok){ addNewStates(q, body, distance, rocks, pattern, depth + 1); } } } void addNewStates(std::list & q, const Body & body, int distance, const std::set & rocks){ for(int i = 0; i < patterns[body.size()].size(); i++){ int pattern = patterns[body.size()][i]; Body newBody = body; addNewStates(q, newBody, distance, rocks, pattern, 0); } } bool isOK(int k){ for(int i = 1; i < 20; i++){ if((k >> i) & (k >> (i - 1))){return false;} } return true; } void init(){ for(int i = 2; i <= 8; i++){ for(int j = 1; j < (1 << i); j++){ if(isOK(j)){ patterns[i].push_back(j); } } } } int main(){ init(); while(true){ int n, k; Point destination; Body body; std::set rocks; std::cin >> n; if(n == 0){break;} for(int i = 0; i < n; i++){ int x, y; std::cin >> x >> y; body.push_back(Point(x, y)); } std::cin >> k; for(int i = 0; i < k; i++){ int x, y; std::cin >> x >> y; rocks.insert(Point(x, y)); } std::cin >> destination.x >> destination.y; std::list q; std::set visited_bodies; q.push_back(State(body, 0)); while(true){ while(visited_bodies.find(q.begin()->body) != visited_bodies.end()){ q.pop_front(); } Body body = q.begin()->body; int distance = q.begin()->distance; if(body[0] == destination){ std::cout << distance << std::endl; break; } visited_bodies.insert(body); q.pop_front(); addNewStates(q, body, distance + 1, rocks); } } }