题目描述
题目要求根据一组地图和地点信息，处理查询请求。每个地图由名称和两个对角坐标定义，每个地点由名称和坐标定义。查询请求包含地点名称和所需的细节级别（detail level\texttt{detail level}detail level）。细节级别按地图面积排序：面积最大的地图为第111级，面积次大的为第222级，依此类推（相同面积的地图视为同一级别）。需要输出满足请求的地图名称，若地点不在任何地图中则输出相应信息，若细节级别超出可用级别则输出最详细（面积最小）的地图。
输入格式
输入分为三个部分：
MAPS：接下来若干行，每行一个地图名称和四个实数（两对角坐标），以LOCATIONS结束。LOCATIONS：接下来若干行，每行一个地点名称和两个实数（坐标），以REQUESTS结束。REQUESTS：接下来若干行，每行一个地点名称和一个正整数（细节级别），以END结束。
输出格式
对于每个请求，输出一行：
- 若地点未知，输出
<location> at detail level <level> unknown location - 若地点不在任何地图中，输出
<location> at detail level <level> no map contains that location - 若细节级别超出可用级别，输出
<location> at detail level <level> no map at that detail level; using <map_name> - 否则，输出
<location> at detail level <level> using <map_name>
样例
输入
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.750.750.75）。
- 若仍相同，则离地图右下角最远（即距离最小）。
- 若仍相同，则选择xxx坐标最小的地图。
地点处理
- 对于每个地点，找出所有包含该地点的地图。
- 将这些地图按上述规则排序，并分配细节级别（相同面积的地图共享同一级别）。
- 记录每个地点的最大细节级别和最详细地图（面积最小）。
请求处理
- 若地点未知，输出
unknown location。 - 若地点没有包含它的地图，输出
no map contains that location。 - 若请求的细节级别超过最大级别，输出最详细地图。
- 否则，输出对应级别的第一个地图（按排序规则）。
复杂度分析
地图数≤100\le 100≤100，地点数≤100\le 100≤100，请求数≤100\le 100≤100，预处理和查询均可接受。
代码实现
// Do You Know the Way to San Jose?// UVa ID: 511// Verdict: Accepted// Submission Date: 2017-04-26// UVa Run Time: 0.000s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constdoubleepsilon=1e-7;structmaps{string name;doublecenterx,centery;doubleleftx,rightx,bottomy,topy;doublearea,ratio;doublecornerx,cornery;};vector<maps>allMaps;map<string,pair<int,int>>locations;map<string,vector<pair<int,int>>>cache;doublewindowRatio=0.75;doublecurrentx,currenty;string name;intlevel,smallest;doubledist(doublex1,doubley1){return(currentx-x1)*(currentx-x1)+(currenty-y1)*(currenty-y1);}boolcmp(inta,intb){if(fabs(allMaps[a].area-allMaps[b].area)<epsilon){doubledist1=dist(allMaps[a].centerx,allMaps[a].centery);doubledist2=dist(allMaps[b].centerx,allMaps[b].centery);if(fabs(dist1-dist2)<epsilon){doublediff1=fabs(allMaps[a].ratio-windowRatio);doublediff2=fabs(allMaps[b].ratio-windowRatio);if(fabs(diff1-diff2)<epsilon){dist1=dist(allMaps[a].cornerx,allMaps[a].cornery);dist2=dist(allMaps[b].cornerx,allMaps[b].cornery);if(fabs(dist1-dist2)<epsilon)returnallMaps[a].leftx<allMaps[b].leftx;elsereturndist1<dist2;}elsereturndiff1<diff2;}elsereturndist1<dist2;}elsereturnallMaps[a].area>allMaps[b].area;}boolreadMap(){doublex1,y1,x2,y2;cin>>name;if(name=="LOCATIONS")returnfalse;cin>>x1>>y1>>x2>>y2;maps m;m.name=name;m.centerx=(x1+x2)/2.0,m.centery=(y1+y2)/2.0;m.leftx=min(x1,x2),m.rightx=max(x1,x2);m.bottomy=min(y1,y2),m.topy=max(y1,y2);m.area=fabs((m.rightx-m.leftx)*(m.topy-m.bottomy));m.ratio=fabs((m.topy-m.bottomy)/(m.rightx-m.leftx));m.cornerx=m.rightx,m.cornery=m.bottomy;allMaps.push_back(m);returntrue;}boolinMap(doublex1,doubley1,maps&m){returnx1>=m.leftx&&x1<=m.rightx&&y1>=m.bottomy&&y1<=m.topy;}boolreadLocation(){doublex1,y1;cin>>name;if(name=="REQUESTS")returnfalse;cin>>x1>>y1;locations.insert(make_pair(name,make_pair(0,0)));vector<int>candidate;for(inti=0;i<allMaps.size();i++)if(inMap(x1,y1,allMaps[i]))candidate.push_back(i);currentx=x1,currenty=y1;sort(candidate.begin(),candidate.end(),cmp);vector<pair<int,int>>info;if(candidate.size()>0){doublearea=allMaps[candidate.front()].area;level=1,smallest=candidate.front();for(inti=0;i<candidate.size();i++){if(fabs(allMaps[candidate[i]].area-area)<epsilon)info.push_back(make_pair(level,candidate[i]));else{level+=1;area=allMaps[candidate[i]].area;info.push_back(make_pair(level,candidate[i]));smallest=candidate[i];}}locations[name].first=level,locations[name].second=smallest;}cache[name]=info;returntrue;}boolreadRequest(){cin>>name;if(name=="END")returnfalse;cin>>level;cout<<name<<" at detail level "<<level;if(locations.find(name)==locations.end())cout<<" unknown location\n";else{if(cache[name].size()==0)cout<<" no map contains that location\n";else{if(level<=locations[name].first){for(autopair:cache[name])if(pair.first==level){cout<<" using "<<allMaps[pair.second].name<<'\n';break;}}else{cout<<" no map at that detail level; using ";cout<<allMaps[locations[name].second].name<<'\n';}}}returntrue;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);cin>>name;while(readMap()){}while(readLocation()){}while(readRequest()){}return0;})
