/* 法一借鉴自： http://blog.csdn.net/zay999abc/article/details/49836073 收获： 1. C++11中的default关键字 最简单易懂的解释： 如果自定义了构造函数，那么默认构造函数就不可以用了，强制=default声明可以让默认构造函数恢复。 有关资料： http://www.cnblogs.com/zhuyijie/p/6464590.html http://blog.csdn.net/a1875566250/article/details/40406883 http://bbs.csdn.net/topics/390689526 2. STL 中的map，可对键值按降序排序 http://www.cnblogs.com/youngforever/articles/3314501.html 3. C++11 中的关键字 bind 和 placeholder 及其有关用法 http://www.cplusplus.com/reference/functional/bind/?kw=bind http://www.cplusplus.com/reference/functional/placeholders/ http://blog.csdn.net/wangshubo1989/article/details/50471709 http://blog.csdn.net/segen_jaa/article/details/51155218 */
#include <iostream>
#include <map>
#include <string>
#include <cmath>
#include <vector>
#include <sstream>
#include <algorithm>
#include <functional> //bind 和 placeholders
using namespace std;
typedef pair<double, double> p_double;
const double EPS = 1e-7;
bool is_dif (const double&a, const double& b) // if is different，实际作用：代替double的不等号
{
return !( fabs(a - b) < EPS);
}
struct Map
{
double x1, y1, x2, y2, area, length, width;
p_double center;
Map() = default;
Map(double a, double b, double c, double d):x1(a), y1(b), x2(c), y2(d)
{
length = max(x1 - x2, y1 - y2); width = min(x1 - x2, y1 - y2);
area = length * width;
double x = (x1 + x2) / 2.0, y = (y1 + y2) / 2.0;
center = make_pair(x, y);
} //在传参数到构造函数前，已经经过了可能需要的交换，以保证 x1 >= x2 && y1 >= y2
};
map<string, map<double, vector<string>, greater<double> > > level; //前一个string表示地点名，double表示的是地图面积（由面积可得其详细等级），之所以map要降序排序，是因为面积越小越详细，详细等级越高，vecto<string>表示的是对于某一地点，有多少详细等级在double的地图，保存其地图名到vector中
map<string, Map> mapInfo; //保存地图名和地图的对应关系
bool isWithin(double x, double y, const Map &m)
{
return x >= m.x2 && x <= m.x1 && y >= m.y2 && y <= m.y1;
}
double distance1 (p_double &p1, p_double &p2)
{
return pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2);
}
bool mycmp(string &s1, string &s2, pair<double, double> &p)
{
Map map1 = mapInfo[s1], map2 = mapInfo[s2];
double d1 = distance1(map1.center, p), d2 = distance1(map2.center, p); //得到两张地图的中心，与该位置的距离
if (is_dif(d1, d2)) return d1 < d2;
double ratio1 = map1.length / map1.width, ratio2 = map2.length / map2.width;
double gap1 = fabs(ratio1 - 0.75), gap2 = fabs(ratio2 - 0.75);
if (is_dif(gap1, gap2)) return gap1 < gap2;
pair<double, double> p1(map1.x1, map1.y2); //地图1的右下角坐标
pair<double, double> p2(map2.x1, map2.y2); //地图2的右下角坐标
double d3 = distance1(p, p1), d4 = distance1(p, p2);
if (is_dif(d3, d4)) return d3 > d4;
return map1.x2 < map2.x2; //对于所有地图，构造时已确保x1>=x2，找最小，自然该从x2找
}
int main()
{
string s;
getline(cin, s);
while (getline(cin, s) && s != "LOCATIONS")
{
string name;
double x1, y1, x2, y2; //分离出地图名和其对角线坐标
istringstream ss(s);
ss >> name >> x1 >> y1 >> x2 >> y2;
if (x1 < x2) swap(x1, x2);
if (y1 < y2) swap(y1, y2); //构造地图前，先确保 x1 >= x2 && y1 >= y2
mapInfo[name] = Map(x1, y1, x2, y2);
}
while(getline(cin, s) && s != "REQUESTS")
{
istringstream ss (s);
string name;
double x, y;
ss >> name >> x >> y;
for (auto &m : mapInfo) //auto是C++11新特性，此处语义为：遍历 mapInfo 中的所有 key_value对，m.first表示的就是 key(string类)，m.second表示的是value(Map对象)
{ //m是 pair(string, Map)
if (isWithin(x, y, m.second))
level[name][m.second.area].push_back(m.first);
}
for (auto &m : level[name])
{ //m是 pair(double, vector<string>)
vector<string> temp(m.second);
pair<double, double> p(x, y);
sort(temp.begin(), temp.end(), bind(mycmp, placeholders::_1, placeholders::_2, p) );
}
}
while (getline(cin, s) && s != "END")
{
istringstream ss (s);
string name;
int n;
ss >> name >> n;
if (!level.count(name)) //没有该地的地名
{
cout << name << " at detail level " << n << " unknown location" << endl;
continue;
}
auto &m = level[name];
if (m.empty()) //没有地图
{
cout << name << " at detail level " << n << " no map contains that location" << endl;
continue;
}
int i = 1; bool flag = false; string tp; //temp
for (auto it = m.begin(); it != m.end(); it++, i++)
{
if (i == n) //找到详细等级为n的地图
{
cout << name << " at detail level " << n << " using " << it->second[0] << endl;
flag = true;
break;
}
if (i == m.size()) tp = it->second[0]; //没找到详细等级为n时，要输出的是最详细的地图
}
if (!flag) cout << name << " at detail level " << n << " no map at that detail level; using " << tp << endl;
}
return 0;
}
/* 法二： 后来又看了一个博主的博客 http://blog.csdn.net/kun768/article/details/43966329 总结他的代码，给我的收获如下 1. hypot函数（可根据直角边求得斜边） http://www.cplusplus.com/reference/cmath/hypot/ 2. 浮点数的相等不等比较，不能用简单地 != 和 == ，一定要用到一个足够小的EPS(一般为1e-7) 这个真是特别汗颜，直到看到这个博主的代码，我才想起来，之前还因为这个WA过，这次侥幸AC，赶紧回去改了下自己的代码...(于是我的代码才有了EPS，本来我忘记这个坑点了，用 != 去比较了...) 3. find_if的写法 这个博主在find_if里面写的...其实我一直都没有看懂，他的原代码是： */
for (auto & i : C1)
i.ilevel = find_if(all_area.begin(), all_area.end(), [i](const double area)
{return fabs(area - i.area) <= EPS; }) - all_area.begin() + 1;/* 然而我几乎查遍了所有find_if的用法，也还是不明白，他为什么可以直接把函数写到find_if的第三个参数 而且这第三个函数也有些看不懂，我曾经试图把它改到外面，做为一个函数，然后find_if的第三个参数只传入函数名进去，但我改了好几次失败了...然而原博主的这种写法，却又一直看不懂 于是最后，我只能把 find_if那段，换成了用find来写，这次很高兴地发现，改对了 */
for (auto & i : C1) i.ilevel = find(all_area.begin(), all_area.end(), i.area) - all_area.begin() + 1;
/* 另附有关find_if函数的一些网站(确实找遍了所有的网站，都没有看到博主这样高端的写法，可能我目前段位太低，此处留坑，希望以后看到，还有机会弄明白) http://www.cplusplus.com/reference/algorithm/find_if/ http://blog.csdn.net/wangshubo1989/article/details/50389811 http://www.cnblogs.com/cy568searchx/archive/2013/08/28/3286684.html -------接着写收获的分割线------- 4. copy_if 和 back_inserter 同样地，我也是只能弄懂语法，但看不太懂博主的代码，此处先留坑，日后有机会再弄懂，我觉得这个博主的这两句代码(find_if那句， copy_if那句)，似乎超出了我目前的知识水平，日后再来细看 */
/* 同时我还看了法三，虽然没有自己敲一次这个方法 法三来自blog： http://blog.csdn.net/wangjinhaowjh/article/details/50563296 法三和法二本质相同，除了用循环代替了我在法二中看不懂写法的find_if和copy_if 虽然，之前查资料时，又看到这段话 假如vector用vector查找复合类型的对象，这个时候一般的想法是写个函数遍历这个vector，然后进行比较查找。实际上在使用STL的时候，不建议使用循环遍历的查找方法，有几个理由 （参见《effictive c++》46条)： 效率：泛型算法通常比循环高效。 正确性: 写循环时比调用泛型算法更容易产生错误。 可维护性: 与相应的显式循环相比，泛型算法通常使代码更干净、更直观。 但是，奈何我现在，真的不太理解法二的泛型算法，实在看不懂，所以，不能走最优解的话，只少应该知道有什么替代的方法，法三就是可以替代的方法 另外，其实unique不是真正的去重，只是将重复的移到末端，要真正去重，还要和 erase一起使用，但就这题而言，按照博主的循环的写法，不用erase不影响AC，但是万一下次的出题方式，导致会影响了呢？ 所以不如将 unique(area.begin(),area.end()); 改为： area.erase(unique(area.begin(),area.end()), area.end()); */