UVA511 Do You Know the Way to San Jose? 题解
UVA511 Do You Know the Way to San Jose? 题解
题目链接：UVA511 Do You Know the Way to San Jose?
题目描述：
互联网现在提供了多种交互式地图设施，用户既可以查看大范围地理区域的概览地图，也可以“放大”到某条具体街道，有时甚至能查看某栋具体建筑所在的更详细地图。例如，圣何塞市中心可能同时出现在加利福尼亚州地图、圣克拉拉县地图以及一张详细街道地图中。
假设你拥有大量矩形地图，并希望设计一个浏览设施，用来处理一系列针对不同地图细节级别地点的地图请求。地点使用地点名称表示。每个地点名称都有唯一的一对实数坐标 \((x,y)\)。每张地图都是唯一的，并带有用于标识的地图名称，且由两对实数坐标 \((x_1,y_1)\) 和 \((x_2,y_2)\) 定义，这两对坐标表示地图的两个对角点。所有地图的边都平行于标准笛卡尔 \(x\) 轴和 \(y\) 轴。地图和地点可以同名。地图的高宽比定义为其高度与宽度之比，其中宽度沿 \(x\) 方向度量，高度沿 \(y\) 方向度量。
一张地图的细节级别可以用该地图所表示的矩形面积来近似；也就是说，假设覆盖面积较小的地图包含更详细的信息。地图之间可以相互重叠。如果一个地点 \((x,y)\) 位于两张或更多面积相等的地图中，则在该细节级别下，优先选择地点离地图中心最近的那张地图。如果该地点到两张同面积重叠地图中心的距离相等，则优先选择高宽比最接近浏览器窗口高宽比 \(0.75\) 的地图。如果这样仍不能打破平局，则优先选择地点离地图右下角最远的那张地图（该启发式规则旨在尽量减少用户浏览器窗口中的滚动需求）。最后，如果仍然并列，则优先选择其 \(x\) 坐标最小的地图。
给定地点可用的最大细节级别，是包含该地点的不同面积地图数量的最大值。显然，不同地点可以有不同的最大细节级别。该地点在细节级别 \(i\) 下的地图，是在包含该地点的不同面积地图的一个最大集合中，面积第 \(i\) 大的地图。因此，该地点在细节级别 \(1\) 下的地图，将是包含该地点的最不详细（面积最大）的地图；而最大细节级别下的地图，将是最详细（面积最小）的地图。
输入格式：
输入文件由一组地图、地点和请求组成，形式如下：
- 单独一行、全部大写的单词
MAPS引入一个包含一张或多张地图的集合。在该集合标题之后，每张地图由一行描述，包含一个地图名称（由字母组成的字符串，不含前导、尾随或嵌入空格）和两对实数坐标 \((x_1,y_1)\)、\((x_2,y_2)\)，表示该地图的两个对角点。- 单独一行、全部大写的单词
LOCATIONS引入一个包含一个或多个地点的集合。在该标题之后，每个地点由一行描述，包含一个地点名称（由字母组成的字符串，不含前导、尾随或嵌入空格）和一对实数坐标 \((x,y)\)，表示该地点的中心。- 单独一行、全部大写的单词
REQUESTS引入一个包含零个或多个请求的集合。在该标题之后，每个请求由一行描述，包含一个地点名称（由字母组成的字符串，不含前导、尾随或嵌入空格），后跟一个正整数，表示该地点所期望的细节级别。- 单独一行、全部大写的单词
END终止文件。请求之前的所有地图和地点数据都是有效的。不会出现重复地图。处理一个有效请求的结果，是包含给定地点且在给定细节级别下的地图名称（使用上述并列打破规则）。无效请求可能由以下原因导致：请求未知地点名称、地点不出现在任何地图中，或细节级别超过包含该地点的不同面积地图数量。
输出格式：
每个请求都必须回显到输出中。如果请求有效，则显示满足该请求的地图名称。如果该地点不在任何地图中，则显示相应提示信息。如果该地点在地图上但细节级别过大，则显示具有最小可用面积（即最大可能细节级别）的地图名称。
数据范围：
题目没说数据范围。
输入样例：
MAPS BayArea -6.0 12.0 -11.0 5.0 SantaClara 4.0 9.0 -3.5 2.5 SanJoseRegion -3.0 10.0 11.0 3.0 CenterCoast -5.0 11.0 1.0 -8.0 SanMateo -5.5 4.0 -12.5 9.0 NCalif -13.0 -7.0 13.0 15.0 LOCATIONS Monterey -4.0 2.0 SanJose -1.0 7.5 Fresno 7.0 0.1 SanFrancisco -10.0 8.6 SantaCruz -4.0 2.0 SanDiego 13.8 -19.3 REQUESTS SanJose 3 SanFrancisco 2 Fresno 2 Stockton 1 SanDiego 2 SanJose 4 SantaCruz 3 END输出样例：
SanJose at detail level 3 using SanJoseRegion SanFrancisco at detail level 2 using BayArea Fresno at detail level 2 no map at that detail level; using NCalif Stockton at detail level 1 unknown location SanDiego at detail level 2 no map contains that location SanJose at detail level 4 using SantaClara SantaCruz at detail level 3 no map at that detail level; using CenterCoast（这题的输入输出太复杂了，就贴一下输入输出样例）
阅读理解 + 大模拟。
大意就是给你平面直角坐标系上的几个地图（矩形）和地点（点），每次询问地点和缩放等级，
然后给出与查询结果最接近的地图是哪张，查询不存在的地点或者缩放等级都是不合法的，差不多这个意思。
坑点在于
原题面是英语的，加大了阅读理解的难度它没说右下角是哪里，实际上是矩形离 \((0,0)\) 距离最远的那个顶点。
也就是说它的坐标系画出来， \(x\) 轴正方向向右侧，\(y\) 轴正方向向下侧。
本题有很多浮点数运算和比较，可以写一个浮点数比较的函数手动控制误差。
它先是说地点和地图都可能存在重名情况，后面又说地图和地点不会重复。
因此可以理解为：地点数据是唯一的；地图数据可以存在重名地图，但不存在完全一样的地图。
没给数据范围，不知道开多大数组，建议使用
vector。
有一些优化用的小技巧，比如地图矩形的面积和高宽比是确定的，可以预处理出来。
还有两点距离公式，由于我们只需要比较两个距离的大小，所以不需要开根号（否则降低精度出错概率增加）
分析一下复杂度。记地图有 \(n\) 个，地点有 \(m\) 个，询问有 \(q\) 个，则复杂度为 \(O(n + m + qn\log n)\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<double, double> pdd;
const double eps = 1e-18;
int dcmp(double x) { if(abs(x) <= eps) return 0; else return x > eps ? 1 : -1; }
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)())
#define Fi first
#define Se second
string str;
struct Maps { string name; double x1, y1, x2, y2, r, S; };
vector<Maps> vec;
unordered_map<string, pdd> mp;
double dis(double x1, double y1, double x2, double y2)
{
const double x = (x1 - x2) * (x1 - x2);
const double y = (y1 - y2) * (y1 - y2);
return x + y;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> str;
while(cin >> str && str != "LOCATIONS") // "MAPS"
{
static double x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
const double _r = abs(y1 - y2) * 1.0 / abs(x1 - x2);
const double _S = abs(x1 - x2) * abs(y1 - y2);
vec.push_back((Maps){str, x1, y1, x2, y2, _r, _S});
}
while(cin >> str && str != "REQUESTS") // "LOCATIONS"
{
static double x, y; cin >> x >> y;
mp[str] = (pdd){x, y};
}
while(cin >> str && str != "END") // "REQUESTS"
{
static int idx; cin >> idx;
cout << str << " at detail level " << idx << ' ';
if(mp.find(str) == mp.end()) { cout << "unknown location\n"; continue; }
pdd qwq = mp[str];
static double x0, y0; x0 = qwq.Fi, y0 = qwq.Se;
static vector<Maps> tmp; tmp.clear();
static vector<double> S; S.clear();
for(auto i : vec)
{
const bool _1 = min(i.x1, i.x2) <= x0 && x0 <= max(i.x1, i.x2);
const bool _2 = min(i.y1, i.y2) <= y0 && y0 <= max(i.y1, i.y2);
if(_1 && _2) { tmp.push_back(i); S.push_back(i.S); }
}
if(tmp.empty()) { cout << "no map contains that location\n"; continue; }
sort(S.begin(), S.end(), greater<double>());
int tot = unique(S.begin(), S.end()) - S.begin();
if(tot < idx) { cout << "no map at that detail level; "; idx = tot; }
static vector<Maps> ans; ans.clear();
for(auto i : tmp) if(dcmp(i.S - S[idx - 1]) == 0) ans.push_back(i);
static auto f = [](const Maps &a, const Maps &b)
{
double c1 = dis((a.x1 + a.x2) / 2.0, (a.y1 + a.y2) / 2.0, x0, y0);
double c2 = dis((b.x1 + b.x2) / 2.0, (b.y1 + b.y2) / 2.0, x0, y0);
int t = dcmp(c1 - c2); if(t != 0) return t < 0;
c1 = abs(a.r - 0.75); c2 = abs(b.r - 0.75);
t = dcmp(c1 - c2); if(t != 0) return t < 0;
c1 = dis(max(a.x1, a.x2), max(a.y1, a.y2), x0, y0);
c2 = dis(max(b.x1, b.x2), max(b.y1, b.y2), x0, y0);
t = dcmp(c1 - c2); if(t != 0) return t > 0;
return min(a.x1, a.x2) < min(b.x1, b.x2);
};
sort(ans.begin(), ans.end(), f);
cout << "using " << ans[0].name << '\n';
}
return 0;
}
