习题5-12(uva-511)

本文主要是介绍习题5-12(uva-511)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在笛卡尔坐标系上，有n张地图，用某条矩形对角线的坐标表示地图范围
m个地名，用坐标表示

输入
地图以 Maps 开始 LOCATIONS 结束
地名以 REQUESTS 结束
查询
地名详细等级
详细等级说明:
所有包含该地名的地图，按面积大小划分等级 1 - k，面积越小等级越高
1.没有该地名
2.有该地名，但是没有地图包含
3.有地图包含，但是没有该等级地图(包含的地图数量小于查询的等级)，输出最详细的
4.有该等级的地图，输出该地图名

#include <iostream>
#include <istream>
#include <sstream>
#include <vector>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <chrono>
#include <ctime>
#include <cmath>
#include <cctype>
#include <string>
#include <cstdio>
#include <iomanip>#include <thread>
#include <mutex>
#include <condition_variable>
#include <functional>
#include <iterator>
using namespace std;
const double Exp = 1e-8;
struct Maps {pair<double, double>  leftTop;pair<double, double>  rightBottom;pair<double, double>  mid;string mapName;double ratio;double area;
};
bool Equal(double a, double b) {return fabs(a - b) < Exp;
}
struct Request {double area;double mdis;double rdis;double rtaio;double xpoint;int id;friend bool operator<(const Request& a, const Request& b) {if (!Equal(a.area,b.area)) return a.area < b.area;else if (!Equal(a.mdis,b.mdis)) return a.mdis < b.mdis;else if (!Equal(a.rtaio , b.rtaio)) return a.rtaio < b.rtaio;else if (!Equal(a.rdis , b.rdis)) return a.rdis < b.rdis;return a.xpoint < b.xpoint;}
};Maps maps[1024];
map<double, set<int> > areas;
unordered_map<string, pair<double,double> > points;set<Request> req;
Maps m;
Request r;int cnt = 0,rcnt = 0;
double tdir[4];void GetName(string& temp, string &name,int &index) {name = "";for (; index < temp.size(); ++index) {if(temp[index] == ' ') break;name += temp[index];}++index;
}double GetValue(string& temp, int& index) {string t = "";for (; index < temp.size(); ++index) {if (temp[index] == ' ') break;t += temp[index];}++index;return atof(t.c_str());
}void FillMap(string &temp) {int index = 0;GetName(temp, m.mapName, index);for (int i = 0; i < 4; ++i) tdir[i] = GetValue(temp, index);m.leftTop.first = min(tdir[0],tdir[2]);m.leftTop.second = max(tdir[1], tdir[3]);m.rightBottom.first = max(tdir[0], tdir[2]);m.rightBottom.second = min(tdir[1], tdir[3]);m.mid.first = (m.leftTop.first + m.rightBottom.first) / 2;m.mid.second = (m.leftTop.second + m.rightBottom.second) / 2;double w = fabs(m.leftTop.first - m.rightBottom.first), h = fabs(m.leftTop.second - m.rightBottom.second);m.area = w * h;m.ratio = w / h;maps[cnt++] = m;
}bool isContain(int id, pair<double, double>& tp) {if (tp.first >= maps[id].leftTop.first && tp.first <= maps[id].rightBottom.first &&tp.second >= maps[id].rightBottom.second && tp.second <= maps[id].leftTop.second) return  true;return false;
}double Distance(pair<double, double>& a, pair<double, double>& b) {return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}int main()
{pair<double, double> tp;string temp,temp2;int index = 0,lev = 0;getline(cin, temp);while (getline(cin, temp) && temp != "LOCATIONS") {FillMap(temp);}while (getline(cin, temp) && temp != "REQUESTS") {index = 0;GetName(temp, temp2, index);tp.first = GetValue(temp, index);tp.second = GetValue(temp, index);points[temp2] = tp;}while (getline(cin, temp) && temp != "END") {index = 0;GetName(temp, temp2, index); lev = GetValue(temp, index);cout << temp2 << " at detail level " << lev;if (points.count(temp2) == 0) {cout << " unknown location" << endl;}else {tp = points[temp2];req.clear(); areas.clear();for (int i = 0; i < cnt; ++i) {if (!isContain(i, tp)) continue;r.id = i;r.area = maps[i].area;r.mdis = Distance(tp, maps[i].mid);r.rdis = Distance(tp, maps[i].rightBottom);r.rtaio = fabs(maps[i].ratio - 0.75);r.xpoint = maps[i].leftTop.first;areas[r.area].insert(i);req.insert(r);}if (req.empty()) {cout << " no map contains that location" << endl;}else {int k = areas.size(),id = -1;set<int>* outList = nullptr;for (auto it = areas.begin(); it != areas.end(); ++it) {if (k == lev) {outList = &it->second;break;}k--;}if (outList == nullptr) {cout << " no map at that detail level; using " << maps[(*req.begin()).id].mapName << endl;continue;}for (auto it = req.begin(); it != req.end(); ++it) {id = it->id;if (outList->count(id)) {cout << " using " << maps[id].mapName << endl;break;}}}}}return 0;
}