问题描述
p511原题链接：UVaOJ 511 - Do You Know the Way to San Jose?
相关说明：本题为《算法竞赛入门经典（第2版）》习题 5-12
解法一：模拟 + 自定义排序
做起来比较繁琐的一题，首先根据输入构造 map<string, realmap> maps 和 map<string, location> locations 用名称来快速进行索引，对于每张地图，需要根据其面积从大到小进行排序，方便后续逐渐增加地图的细节程度等级（面积最大的地图当然细节程度会最低）。这里排序的做法是使用一个 vector<pair<int, string>> map_square, 前者是面积，后者是地图名而非整个地图数据（用地图名可以快速索引到地图信息），这样就能够借助 STL 容器进行排序。针对每个 location 的询问，模拟如下：
- 该 location 是否属于已知地点，未知的话可以直接输出 unknown location, 处理下一个询问；
- 如果 location 已知，则需要留一个标志判断是否有地图包含该地点（默认
false ），并从最大的地图开始遍历（过程中需要维护当前的地图细节等级，每次有新的面积不同的包含该地点的地图出现时 +1）：
- 将含有这个地点且细节等级符合目标的地图放入一个 vector<pair<info, string>> piority 中维护，其中 info 包含各种用于比较的信息，以便对优先级进行排序，最终取 piority[0]；
- 当然，也有可能出现满足细节等级的地图不包含该位置的情况，此时用最后一个（也即面积最小的）包含该地点的地图作为输出；
- 处理时，如果有任何地图包含该地点，记得将标志 no_map_contain 改成 false.
最后的输出就是和上述分的几种情况对应处理，看我的参考实现应该很容易理解。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include <bits/stdc++.h> using namespace std; struct realmap { double x1, y1, x2, y2, mx, my; double square() { return abs(x2 - x1) * abs(y2 - y1); } }; struct location { double x, y; }; struct info { // For compare while sorting the realmap with the same detial level double d1; // distance to the center of the map double d2; // distance of aspect ratio to 0.75 double d3; // distance to the lower right corner of the map double sx; // smallest x-coordinate bool operator<(const info& other) const { if (d1 != other.d1) return d1 < other.d1; else if (d2 != other.d2) return d2 < other.d2; else if (d3 != other.d3) return d3 > other.d3; else return sx < other.sx; } }; bool inside(location& l, realmap& m) { return l.x >= min(m.x1, m.x2) && l.x <= max(m.x1, m.x2) && l.y >= min(m.y1, m.y2) && l.y <= max(m.y1, m.y2); } int main() { int level; string word; cin >> word; // MAPS map<string, realmap> maps; map<string, location> locations; vector<pair<int, string>> map_square; while (cin >> word && word != "LOCATIONS") { cin >> maps[word].x1 >> maps[word].y1 >> maps[word].x2 >> maps[word].y2; maps[word].mx = (maps[word].x1 + maps[word].x2) / 2; maps[word].my = (maps[word].y1 + maps[word].y2) / 2; map_square.push_back(make_pair(maps[word].square(), word)); } sort(map_square.begin(), map_square.end(), greater<pair<int, string>>()); while (cin >> word && word != "REQUESTS") cin >> locations[word].x >> locations[word].y; while (cin >> word >> level && word != "END") { cout << word << " at detail level " << level; if (locations.find(word) == locations.end()) { cout << " unknown location" << endl; continue; } location cur_location = locations[word]; vector<pair<info, string>> piority; string most_detail; int cur_level = 0; double cur_square = -1; bool no_map_contain = true; for (int i = 0; i < map_square.size(); i++) { realmap cur_map = maps[map_square[i].second]; if (inside(cur_location, cur_map)) { no_map_contain = false; if (map_square[i].first != cur_square) { cur_square = map_square[i].first; cur_level += 1; } // to the next detail level if (cur_level == level) piority.push_back( {{pow(cur_location.x - cur_map.mx, 2) + pow(cur_location.y - cur_map.my, 2), abs(abs(cur_map.x1 - cur_map.x2) / abs(cur_map.y1 - cur_map.y2) - 0.75), pow(cur_location.x - max(cur_map.x1, cur_map.x2), 2) + pow(cur_location.y - max(cur_map.y1, cur_map.y2), 2), min(cur_map.x1, cur_map.x2)}, map_square[i].second}); most_detail = map_square[i].second; } } sort(piority.begin(), piority.end()); if (no_map_contain) cout << " no map contains that location" << endl; else if (piority.size()) cout << " using " << piority[0].second << endl; else cout << " no map at that detail level; using " << most_detail << endl; } return 0; } |
|
1 |
#TODO |
