代码块
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000 + 10;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n;
typedef long long ll;
typedef pair<int, int> pi;
#define endl '\n'
typedef pair<int, int> point;
#define x first
#define y second
int getdis (point x, point y) {
return abs(x.x - y.x) + abs(x.y - y.y);
}
struct node {
point top_left, lower_left, top_right, lower_right;
/*
tl --1--- tr
|**********|
3**********4
|**********|
ll --2--- lr
*/
vector<point> edge[5];
int check (point x, int dec) {
if(dec == 1) { // This rectangles is below the given point
if(top_left.y <= x.y && top_left.x <= x.x && top_right.x >= x.x) return x.y - top_left.y;
return -1;
} else if(dec == 2) { // This rectangles is over the given point
if(lower_left.y >= x.y && lower_left.x <= x.x && lower_right.x >= x.x) return lower_left.y - x.y;
return -1;
} else if(dec == 3) { // This rectangles is on the left of the given point
if(top_right.x <= x.x && top_right.y >= x.y && lower_right.y <= x.y) return x.x - top_right.x;
return -1;
} else { // This rectangles is on the right of the given point
if(top_left.x >= x.x && top_left.y >= x.y && lower_left.y <= x.y) return top_left.x - x.x;
return -1;
}
}
}s[N];
map<point, int> _id;
int point_cnt;
int id (point x) {
if(!_id[x]) _id[x] = ++ point_cnt;
return _id[x];
}
namespace graph {
int siz;
vector<pi> g[N * N];
void addedge (int u, int v, int w) {
siz = max(siz, max(u, v));
g[u].push_back({v, w}), g[v].push_back({u, w});
}
int dis[N * N];
bool vis[N * N];
void dijkstra (int s) {
memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
dis[s] = 0;
priority_queue<pi, vector<pi>, greater<pi> > q;
q.push({0, s});
while(!q.empty()) {
int u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
for (auto e : g[u]) {
int v = e.first, w = e.second;
if(dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
q.push({dis[v], v});
}
}
}
}
};
namespace make_graph{
void find_near (point x, int dec) {
// 1 : Down 2 : Up 3 : Left 4 : Right
int pos = -1, minn = inf;
for (int i = 1; i <= n; i ++) {
int len = s[i].check(x, dec);
if(len != -1) {
if(len < minn) minn = len, pos = i;
}
}
if(pos == -1) return;
point y;
if(dec == 1) y = {x.x, x.y - minn}, s[pos].edge[1].push_back(y);
if(dec == 2) y = {x.x, x.y + minn}, s[pos].edge[2].push_back(y);
if(dec == 3) y = {x.x - minn, x.y}, s[pos].edge[4].push_back(y);
if(dec == 4) y = {x.x + minn, x.y}, s[pos].edge[3].push_back(y);
graph::addedge(id(x), id(y), minn);
}
void in_squar(int i) {
for (int k = 1; k <= 4; k ++) {
vector<point> &f = s[i].edge[k];
sort(f.begin(), f.end());
f.erase(unique(f.begin(), f.end()), f.end());
for (int j = 0; j < (int)f.size() - 1; j ++) {
point x = f[j], y = f[j + 1];
graph::addedge(id(x), id(y), getdis(x, y));
}
}
}
};
void init () {
for (int i = 1; i <= point_cnt; i ++) graph::g[i].clear();
for (int i = 1; i <= n; i ++) {
for (int d = 1; d <= 4; d ++)
s[i].edge[d].clear();
}
_id.clear();
point_cnt = 0;
}
void solve () {
init();
point st, ed;
cin >> st.x >> st.y >> ed.x >> ed.y;
cin >> n;
for (int i = 1; i <= n; i ++) {
int x_1, y_1, x_2, y_2;
cin >> x_1 >> y_1 >> x_2 >> y_2;
if(x_1 > x_2) swap(x_1, x_2);
if(y_1 > y_2) swap(y_1, y_2);
s[i].lower_left = {x_1, y_1}, s[i].top_right = {x_2, y_2}, s[i].top_left = {x_1, y_2}, s[i].lower_right = {x_2, y_1};
s[i].edge[1].push_back(s[i].top_left), s[i].edge[1].push_back(s[i].top_right);
s[i].edge[2].push_back(s[i].lower_left), s[i].edge[2].push_back(s[i].lower_right);
s[i].edge[3].push_back(s[i].top_left), s[i].edge[3].push_back(s[i].lower_left);
s[i].edge[4].push_back(s[i].top_right), s[i].edge[4].push_back(s[i].lower_right);
}
for (int i = 1; i <= n; i ++) {
for (int d = 1; d <= 4; d ++)
make_graph::find_near(s[i].top_left, d), make_graph::find_near(s[i].lower_left, d), make_graph::find_near(s[i].top_right, d), make_graph::find_near(s[i].lower_right, d);
}
for (int d = 1; d <= 4; d ++) make_graph::find_near(st, d), make_graph::find_near(ed, d);
for (int i = 1; i <= n; i ++) make_graph::in_squar(i);
id(st), id(ed);
graph::dijkstra(id(st));
if(st.x == ed.x || st.y == ed.y) {
bool flag = 0;
if(st > ed) swap(st, ed);
for (int i = 1; i <= n; i ++) {
if(st.x == ed.x) {
flag |= (s[i].top_left.x <= st.x && s[i].top_right.x >= st.x && s[i].top_left.y >= st.y && s[i].lower_left.y <= ed.y);
} else {
flag |= (s[i].top_left.y >= st.y && s[i].lower_left.y <= st.y && s[i].top_left.x >= st.x && s[i].top_right.x <= ed.x);
}
}
if(flag) {
if(graph::dis[id(ed)] != inf)cout << graph::dis[id(ed)] << endl;
else cout << "No Path" << endl;
} else cout << getdis(st, ed) << endl;
return;
}
if(graph::dis[id(ed)] != inf) cout << graph::dis[id(ed)] << endl;
else cout << "No Path" << endl;
}
signed main() {
// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t --) {
solve();
}
return 0;
}
\KaTeX
- 行内
f_i \to f_{i + 1} - 行间
\begin{aligned} \varphi(n) & = n \times \prod_{i = 1}^s{\frac{p_i - 1}{p_i}} \\\\ & = p_1 \times n' \times \prod_{i = 1}^s{\frac{p_i - 1}{p_i}} \\\\ & = p_1 \times \varphi(n') \end{aligned}
This is a H1 title
This is a H2 title
This is a H3 title
This is a H4 title
This is a H5 title
This is a H6 title
列表
无序
- value 1
- value 1.1
- value 2
- value 3
有序
- value 1
- value 1.1
- value 2
- value 4
清单
- TODO 1
- TODO 2
- TODO 3
标识
加粗：Text
删除线：Text
斜体： Text
行间代码： Text
表格
| Heading | 1 |
|---|---|
| value1 | value2 |
引用
证明： Ice = 冰块
链接
图片
