地图查询 Do You Know the Way to San Jose?

【道路查询】 【背景】 现在互联网提供了多样化的互动式地图，使用户既可以看平面地图也可以“放大”以查看一条具体的街道甚至一栋建筑。比如说，圣荷塞城区可能出现在一幅加利福尼亚州或一幅圣塔克拉拉县的的地图上。现在你有大量的地图，你要拼凑并设计一幅网络互动地图，所以你需要处理地图中详细等级不同的位置的查询。 【题目】 有n张地图(已知名称和某一条对角线两端点的坐标)和m个地名(已知名称和坐标),还有q个查询。 每张地图都是边平行于坐标轴的矩形,比例定义为高度除以宽度的值。每个查询包含一个地名和详细等级i。面积相同的地图总属于同一个详细等级。 假设包含此地名的地图中一共有k种不同的面积,则合法的详细等级为1~k(其中1最不详细,k最详细,面积越小越详细)。 - 如果详细等级i的地图不止一张,则输出地图中心和查询地名最接近的一张 - 如果还有并列的,地图长宽比应尽量接近0.75(这是Web测览器的比例) - 如果还有并列,查询地名和地图右下角的坐标应最远(对应最少的滚动条移动) - 如果还有并列,则输出x坐标最小的一个。 - 如果查询的地名不存在或者没有地图包含它,或者包含它的地图总数超过i,应报告查询非法(如果存在,一并输出包含它的最详细地图名称)。 【输入】 输入文件由一组地图、位置和请求组成，其顺序如下： - 首行输入‘MAP’一词，代表输入地图信息，下面若干行中每行包含地图名（一个没空格的字符串）和某一条对角线两端点的坐标x1,y1,x2,y2(地图都不重复) - 当输入单独一行的‘LOCATION’,停止输入地图，下面若干行开始输入地点名（一个没空格的字符串）和地点坐标x,y - 当输入单独一行的‘REQUESTS’,停止输入地名，下面若干行开始输入请求名（一个没空格的字符串）和一个表示该位置所需详细等级的正整数 - 当输入单独一行的‘END’,停止输入 处理有效请求的结果包含地图的名称和给定位置的坐标。（详见样例） 无效请求包括未知的位置名称、未出现在任何地图中的位置或超过限制level的位置 【输出】 在每一次请求之后输出(斜体为具体字符串) 1.该城市不存在，输出“ _name_ at detail level _level_ unknown location” 2.如果存在输出：“ _name_ at detail level _level_” 3.无效请求： - 如果没有地图包含该位置输出“no map contains that location” - 如果有地图包含该位置，但是没有对应详细等级level的地图，输出最满足要求的地图名称“no map at that detail level; using _MapName_” - 有该详细等级的地图包含该城市输出应该使用的地图名字，“using _MapName_”

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=452 [PDF](https://uva.onlinejudge.org/external/5/p511.pdf) 



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