比赛 2025暑期集训第5场图论专场 评测结果 AAAAAAAAAAA
题目名称 激光 最终得分 100
用户昵称 OTTF 运行时间 1.330 s
代码语言 C++ 内存使用 20.36 MiB
提交时间 2025-07-09 09:46:15
显示代码纯文本

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

using namespace std;

template <typename T>
void read (T& num) {
    T res = 0;
	T ch = getchar();
	T op = 1;

    while (!isdigit (ch) && ch != EOF) {
		op = (ch == '-' ? -1 : 1);
        ch = getchar ();
	}

    while (isdigit (ch)) {
        res = (res * 10) + (ch - '0');
        ch = getchar ();
    }
    num = op * res;
}

class Read {
	public:
	Read operator>> (auto& other) {
		read (other);
		return (*this);
	}
};

Read in;

const int N = 114514;

long long n;
long long xl;
long long yl;
long long xb;
long long yb;
map<int, set<int>> lines;
map<int, set<int>> rows;
map<pair<int, int>, int> mp;
vector<pair<int, int>> graph[N * 2];
int dis[N * 2];
bool flag[N * 2];

inline void addPoint (int x, int y) {
	lines[x].insert(y);
	rows[y].insert(x);
}

inline void addRoad (int u, int v, int w, bool b) {
	if (b) {
		if (u != 0 && u != 2 * n + 1) {
			u += n;
		}
		if (v != 0 && v != 2 * n + 1) {
			v += n;
		}
	}

	graph[u].emplace_back(v, w);
	graph[v].emplace_back(u, w);
}

int main () {
	
	freopen ("lasers.in", "r", stdin);
	freopen ("lasers.out", "w", stdout);

	in >> n >> xl >> yl >> xb >> yb;
	addPoint (xl, yl);
	addPoint (xb, yb);
	mp[make_pair (xl, yl)] = 0;
	mp[make_pair (xb, yb)] = n * 2 + 1;

	int x, y;
	for (int i = 1; i <= n; i++) {
		in >> x >> y;
		addPoint (x, y);
		mp[make_pair (x, y)] = i;
		
		addRoad (mp[make_pair (x, y)], mp[make_pair (x, y)] + n, 1, false);
	}

	for (auto [i, line] : lines) {
		for (auto iter = line.begin(), then = ++line.begin(); then != line.end(); iter++, then++) {
			addRoad (mp[make_pair (i, *iter)], mp[make_pair (i, *then)], 0, false);
		}
	}
	for (auto [i, row] : rows) {
		for (auto iter = row.begin(), then = ++row.begin(); then != row.end(); iter++, then++) {
			addRoad (mp[make_pair (*iter, i)], mp[make_pair (*then, i)], 0, true);
		}
	}

	fill (dis, dis + 2 * n + 1 + 1, 1e9);
	dis[0] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.emplace(0, 0);

	while (!pq.empty()) {
		auto [_, u] = pq.top();
		pq.pop();
		if (flag[u]) {
			continue;
		}
		flag[u] = true;

		for (auto[v, c] : graph[u]) {
			if (dis[v] > dis[u] + c) {
				dis[v] = dis[u] + c; 
				pq.emplace(dis[v], v);
			}
		}
	}

	if (dis[2 * n + 1] == 1e9) {
		cout << -1 << endl;
		return 0;
	}

	cout << dis[2 * n + 1] << endl;
	
	return 0;
}