Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- const int maxn = 600 + 100;
- const LL INF = 0x3f3f3f3f3f3f3f3f;
- struct Node {
- int x, h1, h2;
- };
- int n, m, k, T, sx, sy, tx, ty;
- LL ans;
- LL dis[maxn][maxn];
- Node node[maxn];
- pair<int, int> findLR(int x, int y) {
- pair<int, int> p(-1, -1);
- for (int i = 0; i < k; ++i) {
- if (node[i].h1 <= y && node[i].h2 >= y) {
- if (node[i].x <= x) {
- if (p.first == -1) {
- p.first = i;
- } else {
- if (node[p.first].x < node[i].x) {
- p.first = i;
- }
- }
- }
- if (node[i].x >= x) {
- if (p.second == -1) {
- p.second = i;
- } else {
- if (node[p.second].x > node[i].x) {
- p.second = i;
- }
- }
- }
- }
- }
- return p;
- }
- LL calDis(int sidx, int tidx) {
- if (sidx == -1 || tidx == -1) {
- return INF;
- }
- if (dis[sidx << 1][tidx << 1 | 1] == INF) {
- return INF;
- }
- return dis[sidx << 1][tidx << 1 | 1]
- - (node[tidx].h2 - ty)
- - (sy - node[sidx].h1)
- + abs(sx - node[sidx].x)
- + abs(tx - node[tidx].x);
- }
- int main() {
- #ifdef ExRoc
- freopen("test.txt", "r", stdin);
- #endif // ExRoc
- ios::sync_with_stdio(false);
- cin >> n >> m >> k;
- memset(dis, 0x3f, sizeof(dis));
- for (int i = 0; i < k; ++i) {
- cin >> node[i].x >> node[i].h1 >> node[i].h2;
- }
- for (int i = 0; i < k; ++i) {
- for (int j = 0; j < k; ++j) {
- if (i == j) {
- dis[i << 1][j << 1] = dis[i << 1 | 1][j << 1 | 1] = 0;
- dis[i << 1][j << 1 | 1] = dis[i << 1 | 1][j << 1] = node[i].h2 - node[i].h1;
- continue;
- }
- if (node[i].h1 >= node[j].h1 && node[i].h1 <= node[j].h2) {
- dis[i << 1][j << 1] = dis[j << 1][i << 1] = abs(node[i].x - node[j].x) + (node[i].h1 - node[j].h1);
- dis[i << 1][j << 1 | 1] = dis[j << 1 | 1][i << 1] = abs(node[i].x - node[j].x) + (node[j].h2 - node[i].h1);
- }
- if (node[i].h2 >= node[j].h1 && node[i].h2 <= node[j].h2) {
- dis[i << 1 | 1][j << 1] = dis[j << 1][i << 1 | 1] = abs(node[i].x - node[j].x) + (node[i].h2 - node[j].h1);
- dis[i << 1 | 1][j << 1 | 1] = dis[j << 1 | 1][i << 1 | 1] = abs(node[i].x - node[j].x) + (node[j].h2 - node[i].h2);
- }
- }
- }
- int k2 = k << 1;
- for (int kk = 0; kk < k2; ++kk) {
- for (int i = 0; i < k2; ++i) {
- for (int j = 0; j < k2; ++j) {
- dis[i][j] = min(dis[i][j], dis[i][kk] + dis[kk][j]);
- }
- }
- }
- cin >> T;
- while (T--) {
- cin >> sx >> sy >> tx >> ty;
- if (sy == ty) {
- cout << abs(sx - tx) << endl;
- continue;
- }
- if (sy > ty) {
- swap(sx, tx);
- swap(sy, ty);
- }
- pair<int, int> sp = findLR(sx, sy);
- pair<int, int> tp = findLR(tx, ty);
- ans = min({calDis(sp.first, tp.first), calDis(sp.first, tp.second), calDis(sp.second, tp.first), calDis(sp.second, tp.second)});
- cout << (ans == INF ? -1 : ans) << endl;
- }
- return 0;
- }
Advertisement
Advertisement
