XieNaoban's Blog
0%

算法竞赛入门经典(第2版) 5-12UVa511 - Do You Know the Way to San Jose

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 3.2k 阅读时长 ≈ 3 分钟

题意：N张地图，查找某地点在不在某些地图上，若在，使用细节多的地图。使用哪个地图的破要求挺多，细心一点就好。

代码：（Accepted，0.000s） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
//UVa511 - Do You Know the Way to San Jose?
//Accepted 0.000s
//#define _XIENAOBAN_
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
#define EPS 1e-7

struct mapdat {
	float area,ratio, midx, midy, x1, y1, x2, y2;
	int level;
	string name;
	mapdat(char* n, float& t1, float& t2, float& t3, float& t4) :name(n), midx((t1 + t3) / 2), midy((t2 + t4) / 2) {
		if (t1 < t3) x1 = t1, x2 = t3;
		else x1 = t3, x2 = t1;
		if (t2 < t4) y1 = t2, y2 = t4;
		else y1 = t4, y2 = t2;
		area = (x2 - x1)*(y2 - y1);
		ratio = (float)fabs((y2 - y1) / (x2 - x1) - 0.75);
	}
};

inline bool findloc(const mapdat& m, float& x, float& y) {
	return x > m.x1&&x<m.x2&&y>m.y1&&y < m.y2;
}

inline float dist(const mapdat& m, float& x, float& y) {
	return (x - m.midx)*(x - m.midx) + (y - m.midy)*(y - m.midy);
}

vector<mapdat> maps;
map<string, pair<float, float> > locs;
char stmp[80];
int l, lev(0);
float t1, t2, t3, t4;

int main()
{
#ifdef _XIENAOBAN_
#define gets(T) gets_s(T, 80)
	freopen("in.txt", "r", stdin);
#endif
	gets(stmp);
	while (scanf("%s", stmp) != EOF && strcmp(stmp, "LOCATIONS")) {
		scanf("%f%f%f%f", &t1, &t2, &t3, &t4);
		maps.push_back(mapdat(stmp, t1, t2, t3, t4));
	}

	sort(maps.begin(), maps.end(), [](mapdat& a, mapdat& b) {return a.area > b.area;});
	float a(-1.0);
	for (auto& r : maps) {
		if (fabs(r.area - a)>EPS)
			r.level = ++lev, a = r.area;
		else r.level = lev;
	}
	//for (auto& r : maps) cout << r.level << ' ' << r.name << '\t' << r.midx << ' ' << r.midy << ' ' << r.area << endl;//
	while (scanf("%s", stmp) != EOF && strcmp(stmp, "REQUESTS")) {
		scanf("%f%f", &t1, &t2);
		locs[stmp] = make_pair(t1, t2);
	}
	while (scanf("%s", stmp) != EOF && strcmp(stmp, "END")) {
		scanf("%d", &l);
		printf("%s at detail level %d ", stmp, l);
		auto nowloc(locs.find(stmp));
		if (nowloc == locs.end()) {
			printf("unknown location\n");
			continue;
		}
		vector<mapdat> m,nm;
		for (const auto& r : maps)
			if (findloc(r, nowloc->second.first, nowloc->second.second))
				if(r.level!=l)m.push_back(r);
				else nm.push_back(r);
		if (m.empty()) {
			printf("no map contains that location\n");
			continue;
		}
		auto cmp = [&nowloc](mapdat& a, mapdat& b)->bool {
			auto& X(nowloc->second.first),& Y(nowloc->second.second);
			if (a.level != b.level) return a.level > b.level;
			auto da(dist(a, X, Y)),db(dist(b, X, Y));
			if (fabs(da - db) > EPS) return da < db;
			if (fabs(a.ratio - b.ratio) > EPS) return a.ratio < b.ratio;
			da = (X - a.x2)*(X - a.x2) + (Y - a.y1)*(Y - a.y1);
			db = (X - b.x2)*(X - b.x2) + (Y - b.y1)*(Y - b.y1);
			if (fabs(db - da) > EPS) return da > db;
			return a.x1 < b.x1;
		};
		if (nm.empty()) {
			sort(m.begin(), m.end(), cmp);
			if (m[0].level < l) printf("no map at that detail level; ");
			printf("using %s\n", m[0].name.c_str());
			continue;
		}
		sort(nm.begin(), nm.end(), cmp);
		printf("using %s\n", nm[0].name.c_str());
	}
	return 0;
}

分析：状态不好没认真编，编的比较乱比较丑。还没开始优化，想着先提交个试试，结果这也0.000s通过了。。。看来数据比较水。那就不改动不优化了。