比赛 20161223 评测结果 AAAAAAAAAAA
题目名称 激光 最终得分 100
用户昵称 confoo 运行时间 0.600 s
代码语言 C++ 内存使用 161.29 MiB
提交时间 2016-12-23 19:48:09
显示代码纯文本
//sro FarmerJohn orz
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
#include <vector>
#define file(x) "lasers." #x
using std::min;
const int N = 1e5 + 10, V = N << 2, INF = 0x3f3f3f3f, E = 1e7;
inline int zip(int u, int d) {return u*4 + d;}
int n, x[N], y[N], cor[N << 1], dis[V], xb, yb, ans;
std::vector<int> yp[N], xp[N];
int tmp[N];
struct EDGE{int u, v, w;}st[E];
int hed[V], nxt[E], sz;
void add(int u, int v, int w) {
	st[++sz] = (EDGE){u, v, w};
	nxt[sz] = hed[u], hed[u] =sz;
}
void lisan(int x[N], int& ls) {
	ls = 0;
	std::map<int, int> rk;
	memcpy(tmp, x, sizeof(tmp));
	std::sort(tmp + 1, tmp + 1 + n);
	for (int i = 1; i <= n; i++) {
		rk[tmp[i]] = ++ls;
		while (i + 1 <= n && tmp[i + 1] == tmp[i]) ++i;
	}
	for (int i = 1; i <= n; i++) x[i] = rk[x[i]];
}
std::queue<int> q;
bool inq[V];
int posx[N], posy[N];
bool cmpx(int a, int b) {return x[a] < x[b];}
bool cmpy(int a, int b) {return y[a] < y[b];}
int main() {
	freopen(file(in), "r", stdin);
	freopen(file(out), "w", stdout);
	scanf("%d", &n);
	n += 2;
	for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]);
	lisan(x, xb), lisan(y, yb);
	for (int i = 1; i <= n; i++) xp[x[i]].push_back(i), yp[y[i]].push_back(i);
	for (int i = 1; i <= xb; i++) {
		std::sort(xp[i].begin(), xp[i].end(), cmpy);
		for (int j = 0; j < xp[i].size(); j++) posx[xp[i][j]] = j; 
	}
	for (int i = 1; i <= yb; i++) {
		std::sort(yp[i].begin(), yp[i].end(), cmpx);
		for (int j = 0; j < yp[i].size(); j++) posy[yp[i][j]] = j; 
	}
	for (int u = 1; u <= n; u++)
		for(int d = 0; d < 4; d++) for (int dd = -1; dd <= 1; dd++) {
			int nd = (d + dd + 4)%4, c = -1;
			if (nd == 0) if(posx[u] + 1 < xp[x[u]].size()) c = xp[x[u]][posx[u] + 1];else;
			else if (nd == 2) if(posx[u] - 1 >= 0) c = xp[x[u]][posx[u] - 1];else;
			else if (nd == 1) if(posy[u] + 1 < yp[y[u]].size()) c = yp[y[u]][posy[u] + 1];else;
			else if (nd == 3) if(posy[u] - 1 >= 0) c = yp[y[u]][posy[u] - 1];else;
			if (c != -1) add(zip(u, d), zip(c, nd), dd != 0);
	}
	memset(dis, 0x3f, sizeof(dis));
	for (int d = 0, u; d < 4; d++) dis[u = zip(1, d)] = 0, inq[u] = 1, q.push(u);
	while (!q.empty()) {
		int u = q.front();q.pop();
		for (int e = hed[u], v; v = st[e].v; e = nxt[e]) if (dis[v] > dis[u] + st[e].w) {
			dis[v] = dis[u] + st[e].w;
			if (!inq[v]) inq[v] = 1, q.push(v);
		}
		inq[u] = 0;
	}
	int ans = INF;
	for (int d = 0; d < 4; d++) ans = min(ans, dis[zip(2, d)]);
	printf("%d", ans == INF ? -1 : ans);
}