ACMP 979. Формула 001

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

const int N = 1000;

int n, x[N], y[N];
std::map<std::pair<int, int>, int> vv;
bool u[N][N];
pair<int, int> p[N][N];
int dx[9] = { -1, -1, -1,  0, 0, 0,  1, 1, 1 };
int dy[9] = { -1,  0,  1, -1, 0, 1, -1, 0, 1 };

void aiok(std::queue<pair<int, int>>& q, int i, int v, int x, int y) {
    if(vv.count({x, y})) {
        int z = vv[{x, y}];
        if(!u[v][z]) p[v][z] = {i, v}, u[v][z] = 1, q.push({v, z});
    }
}

int main() {
    std::cin >> n;
    for(int i = 0; i < n; ++i) std::cin >> x[i] >> y[i];
    for(int i = 0; i < n; ++i) vv[{x[i], y[i]}] = i;
    std::queue<pair<int, int>> q; q.push({0, 0}); u[0][0] = 1;
    while(!q.empty()) {
        auto v = q.front(); q.pop();
        const int pv = v.first, cv = v.second;
        const int mx = 2*x[cv]-x[pv], my = 2*y[cv]-y[pv];
        //std::cout << pv << "; " << cv << endl;

        if(cv == n-1) {
            vector<int> res;
            for(int i=pv, j=cv; i+j != 0; ) {
                int a = i, b = j;
                res.push_back(j);
                i = p[a][b].first;
                j = p[a][b].second;
            }

            reverse(res.begin(), res.end());
            std::cout << res.size() << std::endl << "1 ";
            for(int v : res) cout << v+1 << ' ';
            return 0;
        }

        for(int i = 0; i < 9; ++i)  {
            const int ax=mx+dx[i], ay=my+dy[i];
            aiok(q, pv, cv, ax, ay);
        }
    }

    std::cout << -1;
}