记录编号	603403	评测结果	AAAAAATTTTA
题目名称	2578.激光	最终得分	64
用户昵称	LikableP	是否通过	未通过
代码语言	C++	运行时间	8.103 s
提交时间	2025-07-11 16:29:50	内存使用	10.05 MiB

#include <algorithm>
#include <cstdio>
#include <queue>
typedef long long ll;

void ParseIn();
void Core();
void WriteOut();

int main() {
  freopen("lasers.in", "r", stdin);
  freopen("lasers.out", "w", stdout);
  ParseIn();
  Core();
  WriteOut();
  return 0;
}

template <typename T> T read();
template <typename T> void write(T, char);

const int MAXN = 1e5 + 10;

int n, sx, sy, ex, ey;
int x[MAXN], y[MAXN];
void ParseIn() {
  n = read<int>(), sx = read<int>(), sy = read<int>(), ex = read<int>(), ey = read<int>();
  for (int i = 1; i <= n; ++i) {
    x[i] = read<int>(), y[i] = read<int>();
  }
  x[0] = sx, y[0] = sy;
  ++n;
  x[n] = ex, y[n] = ey;
}

struct NODE {
  int x, y, step, id;
};
::std::queue<NODE> q;
::std::vector<int> xs[MAXN], ys[MAXN];
int vis[MAXN];
int b[MAXN];
int ans;
void Core() {
  // 离散化
  for (int i = 0; i <= n; ++i) b[i] = x[i];
  ::std::sort(b, b + n + 1);
  int len = ::std::unique(b, b + n + 1) - b;
  for (int i = 0; i <= n; ++i) x[i] = ::std::lower_bound(b, b + len, x[i]) - b;
  for (int i = 0; i <= n; ++i) b[i] = y[i];
  ::std::sort(b, b + n + 1);
  len = ::std::unique(b, b + n + 1) - b;
  for (int i = 0; i <= n; ++i) y[i] = ::std::lower_bound(b, b + len, y[i]) - b;
  // for (int i = 0; i <= n; ++i) printf("{%d %d}\n", x[i], y[i]);

  for (int i = 0; i <= n; ++i) xs[x[i]].push_back(i), ys[y[i]].push_back(i);

  // bfs
  q.push({x[0], y[0], 0, 0});
  while (!q.empty()) {
    int nx = q.front().x, ny = q.front().y, nstep = q.front().step, nid = q.front().id;
    // printf("[%d %d %d %d]\n", nx, ny, nstep, nid);
    if (nx == x[n] && ny == y[n]) {
      ans = nstep;
      return;
    }
    q.pop();
    for (auto item : xs[nx]) {
      if (item == nid) continue;
      vis[item]++;
      if (vis[item] > 2) continue;
      q.push({x[item], y[item], nstep + 1, item});
    }
    for (auto item : ys[ny]) {
      if (item == nid) continue;
      vis[item]++;
      if (vis[item] > 2) continue;
      q.push({x[item], y[item], nstep + 1, item});
    }
  }
}

void WriteOut() {
  write(ans - 1, '\n');
}

#define isdigit(ch) (ch >= '0' && ch <= '9')
template <typename T> T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}
#undef isdigit

template <typename T> void write(T x, char ed) {
  if (x < 0) x = -x, putchar('-');
  int sta[sizeof(T) << 2], top = 0;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while (x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
  putchar(ed);
}