Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int inf = 1e9;
- const int K = 30 + 10;
- using pi = pair <int, int>;
- struct Hole{int x1, y1, x2, y2;};
- struct Point{int x, y;};
- vector <pi> point;
- Hole hole[K];
- int sz;
- int Index(int x, int y){
- int l = 0, r = sz - 1;
- while(l <= r){
- int mid = (l + r) / 2;
- if(point[mid].first == x and point[mid].second == y) return mid;
- else if(point[mid].first == x){
- if(point[mid].second < y) l = mid + 1;
- else r = mid - 1;
- }
- else if(point[mid].first < x) l = mid + 1;
- else r = mid - 1;
- }
- }
- int Dist(int x1, int y1, int x2, int y2){
- return abs(x1 - x2) + abs(y1 - y2);
- }
- int main(){
- int k,Q;
- scanf("%d %d", &k, &Q);
- for(int i=1;i<=k;i++){
- int x1, y1, x2, y2;
- scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
- hole[i] = {x1, y1, x2, y2};
- point.push_back({x1, y1});
- point.push_back({x2, y2});
- }
- sort(point.begin(), point.end());
- point.resize( unique(point.begin(), point.end()) - point.begin());
- sz = point.size();
- int dis[sz + 1][sz + 1];
- for(int i=0;i<sz;i++){
- for(int j=0;j<sz;j++){
- dis[i][j] = (i == j ? 0:
- Dist(point[i].first, point[i].second, point[j].first, point[j].second));
- }
- }
- for(int i=1;i<=k;i++){
- int idx1 = Index(hole[i].x1, hole[i].y1);
- int idx2 = Index(hole[i].x2, hole[i].y2);
- dis[ idx1 ][ idx2 ] = dis[ idx2 ][ idx1 ] = 0;
- }
- for(int k=0;k<sz;k++){
- for(int i=0;i<sz;i++){
- for(int j=0;j<sz;j++){
- dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
- }
- }
- }
- for(int q=1;q<=Q;q++){
- int ux, uy, vx, vy;
- scanf("%d %d %d %d", &ux, &uy, &vx, &vy);
- int mn = Dist(ux, uy, vx, vy);
- for(int i=0;i<sz;i++){
- for(int j=i+1;j<sz;j++){
- mn = min({mn,
- Dist(ux, uy, point[i].first, point[i].second) + dis[i][j] + Dist(point[j].first, point[j].second, vx, vy),
- Dist(vx, vy, point[i].first, point[i].second) + dis[i][j] + Dist(point[j].first, point[j].second, ux, uy)
- });
- }
- }
- printf("%d\n", mn);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement