比赛 |
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;
}