UVa 511 Do You Know the Way to San Jose

题目描述题目要求根据一组地图和地点信息处理查询请求。每个地图由名称和两个对角坐标定义每个地点由名称和坐标定义。查询请求包含地点名称和所需的细节级别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//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constdoubleepsilon1e-7;structmaps{string name;doublecenterx,centery;doubleleftx,rightx,bottomy,topy;doublearea,ratio;doublecornerx,cornery;};vectormapsallMaps;mapstring,pairint,intlocations;mapstring,vectorpairint,intcache;doublewindowRatio0.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){doubledist1dist(allMaps[a].centerx,allMaps[a].centery);doubledist2dist(allMaps[b].centerx,allMaps[b].centery);if(fabs(dist1-dist2)epsilon){doublediff1fabs(allMaps[a].ratio-windowRatio);doublediff2fabs(allMaps[b].ratio-windowRatio);if(fabs(diff1-diff2)epsilon){dist1dist(allMaps[a].cornerx,allMaps[a].cornery);dist2dist(allMaps[b].cornerx,allMaps[b].cornery);if(fabs(dist1-dist2)epsilon)returnallMaps[a].leftxallMaps[b].leftx;elsereturndist1dist2;}elsereturndiff1diff2;}elsereturndist1dist2;}elsereturnallMaps[a].areaallMaps[b].area;}boolreadMap(){doublex1,y1,x2,y2;cinname;if(nameLOCATIONS)returnfalse;cinx1y1x2y2;maps m;m.namename;m.centerx(x1x2)/2.0,m.centery(y1y2)/2.0;m.leftxmin(x1,x2),m.rightxmax(x1,x2);m.bottomymin(y1,y2),m.topymax(y1,y2);m.areafabs((m.rightx-m.leftx)*(m.topy-m.bottomy));m.ratiofabs((m.topy-m.bottomy)/(m.rightx-m.leftx));m.cornerxm.rightx,m.cornerym.bottomy;allMaps.push_back(m);returntrue;}boolinMap(doublex1,doubley1,mapsm){returnx1m.leftxx1m.rightxy1m.bottomyy1m.topy;}boolreadLocation(){doublex1,y1;cinname;if(nameREQUESTS)returnfalse;cinx1y1;locations.insert(make_pair(name,make_pair(0,0)));vectorintcandidate;for(inti0;iallMaps.size();i)if(inMap(x1,y1,allMaps[i]))candidate.push_back(i);currentxx1,currentyy1;sort(candidate.begin(),candidate.end(),cmp);vectorpairint,intinfo;if(candidate.size()0){doubleareaallMaps[candidate.front()].area;level1,smallestcandidate.front();for(inti0;icandidate.size();i){if(fabs(allMaps[candidate[i]].area-area)epsilon)info.push_back(make_pair(level,candidate[i]));else{level1;areaallMaps[candidate[i]].area;info.push_back(make_pair(level,candidate[i]));smallestcandidate[i];}}locations[name].firstlevel,locations[name].secondsmallest;}cache[name]info;returntrue;}boolreadRequest(){cinname;if(nameEND)returnfalse;cinlevel;coutname 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(levellocations[name].first){for(autopair:cache[name])if(pair.firstlevel){cout using allMaps[pair.second].name\n;break;}}else{cout no map at that detail level; using ;coutallMaps[locations[name].second].name\n;}}}returntrue;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);cinname;while(readMap()){}while(readLocation()){}while(readRequest()){}return0;}